51Nod 1043 幸运号码

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 const int mod = 1e9 + 7;
 7 int dp[1010][10000];
 8 // dp[i][j] : i 个数，组成总和为j 的数量
 9 
10 int main()
11 {
12     int n;
13     scanf("%d", &n);
14     dp[0][0] = 1;
15     for (int i = 0; i <= 9; i++)
16         dp[1][i] = 1;
17     for (int i = 2; i <= n; i++)
18     {
19         for (int j = 0; j <= 9 * i; j++)
20         {
21             int sum = 0;
22             for (int k = 0; k <= 9; k++)
23             {
24                 if (j >= k)
25                     sum = (sum + dp[i - 1][j - k]) % mod;
26                 else
27                     break;
28             }
29             dp[i][j] = sum;
30         }
31     }
32     ll ans = 0;
33     for (int i = 0; i <= 9 * n; i++)
34         ans = (ans + (ll)dp[n][i] * (dp[n][i] - dp[n - 1][i])) % mod;
35     printf("%lld
", ans);
36     return 0;
37 }