Codeforces 258B Little Elephant and Elections

题意：有7个人从m个数中任选一个不重复的，其中4和7是幸运数，一个人的幸运值等于他所选的数字中所有'4'的个数+'7'的个数。求一个人的幸运值比其他6人幸运值总和大的方案数。

 1 #include <iostream>
 2 #define MOD 1000000007
 3 using namespace std;
 4 typedef long long LL;
 5 LL dp[11][11];
 6 LL f[11],ans;
 7 int bit[11],len;
 8 void init(){
 9     dp[1][0] = 8;dp[1][1] = 2;
10     for(int i = 2;i <= 10;i++){
11         for(int j = 0;j <= i;j++){
12             if(j)   dp[i][j] += dp[i-1][j-1]*2;
13             dp[i][j] += dp[i-1][j]*8;
14         }
15     }
16 }
17 
18 void cal(LL x){
19     len = 0;
20     while(x){
21         bit[len++] = x%10;
22         x /= 10;
23     }
24     int cnt = 0;
25     for(int i = len-1;i >= 0;i--){
26         for(int j = 0;j < bit[i];j++){
27             int c = (j == 4 || j == 7) ? 1 : 0;
28             for(int k = 0;k <= 10;k++){
29                 if(cnt+c+k > 10)    break;
30                 f[cnt+c+k] = (f[cnt+c+k]+dp[i][k]) % MOD;
31             }
32             if(i == 0)  f[cnt+c] = (f[cnt+c]+1) % MOD;
33         }
34         if(bit[i] == 4 || bit[i] == 7)  cnt++;
35     }
36     f[cnt]++;f[0]--;
37 }
38 
39 void dfs(int dep,int sum,LL cnt){
40     if(sum >= len)   return;
41     if(dep == 6){
42         for(int i = sum+1;i <= len;i++){
43             ans = (ans + cnt*f[i]) % MOD;
44         }
45         return;
46     }
47     for(int i = 0;i < len;i++){
48         f[i]--;
49         dfs(dep+1,sum+i,cnt*(f[i]+1)%MOD);
50         f[i]++;
51     }
52 }
53 
54 int main()
55 {
56     LL n;
57     cin>>n;
58     init();
59     cal(n);
60     ans = 0;
61     dfs(0,0,1);
62     cout<<ans<<endl;
63     return 0;
64 }

View Code