【洛谷】T160513 E - 运气

发表于 更新于 分类于 Valine：
本文字数： 98 阅读时长 ≈ 1 分钟

T160513 E - 运气

思路

  1. dfs取数，然后判断当前数是否为符合题目要求
  2. 将枚举的所有数字组合成一个整数 
    1
    2
    3
    4
    for(int i=0;i<len;i++)
    {
        sum=sum*10+s[i];
    }

代码

  1. 7.70s/632.00KB/487B C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;
const int N = 15,mod=1e9+7;
int a[N];
bool st[N];
int n,k;
long long res;

void check(){
    long long temp=0;
    for(int i=0;i<n;i++){
        temp=temp*10+a[i];
    }
    if(temp%k==0)res++;
}

void dfs(int u){
    if(u==n){
        check();
        return;
    }
    
    for(int i=1;i<=6;i++){
        a[u]=i;
        dfs(u+1);
    }
}

int main(){
    cin>>n>>k;
    dfs(0);
    cout<<res%mod<<endl;
    return 0;
}
  1. 8.17s / 624.00KB / 466B C++11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int n,k;
int s[10];
long long MOD=(1000000000+7);
long long ans;
void dfs(int len){
    if(len==n){
        long long sum=0;
        for(int i=0;i<len;i++){
            sum=sum*10+s[i];
        }
        //cout<<sum<<endl;
        if(sum%k==0){
            ans++;
            ans=ans%MOD;
        }
        return;
    }
    for(int i=1;i<=6;i++){
        s[len]=i;
        dfs(len+1);
    }
}
int main(){
    
    while(cin>>n>>k){
        ans=0;
        dfs(0);
        cout<<ans<<endl;
    }
    return 0;
}