题意：有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(){ 9dp[1][0] = 8;dp[1][1] = 2;10for(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){19len = 0;20while(x){21 bit[len++] = x%10;22 x /= 10;23}24int cnt = 0;25for(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}36f[cnt]++;f[0]--;37 }38 39 void dfs(int dep,int sum,LL cnt){40if(sum >= len) return;41if(dep == 6){42 for(int i = sum+1;i <= len;i++){43 ans = (ans + cnt*f[i]) % MOD;44 }45 return;46}47for(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 {56LL n;57cin>>n;58init();59cal(n);60ans = 0;61dfs(0,0,1);62cout<<ans<<endl;63return 0;64 }
View Code
