51nod 1043 数位dp

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1043

1043 幸运号码

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

1个长度为2N的数，如果左边N个数的和 = 右边N个数的和，那么就是一个幸运号码。

例如：99、1230、123312是幸运号码。

给出一个N，求长度为2N的幸运号码的数量。由于数量很大，输出数量 Mod 10^9 + 7的结果即可。

Input

输入N(1<= N <= 1000)

Output

输出幸运号码的数量 Mod 10^9 + 7

Input示例

Output示例

9
dp[i][j]表示位数为j各位数字和为i的方案个数，一开始我去除了前导零的影响，统计时的复杂度就会高，导致一直有几个点过不去。
后来发现其实可以算上有前导零的最后能在O(1)内减去他，降低了复杂度而且空间也能降维了，因为只需要最后两组数据，皆大欢喜。
dp[i][j]=SUM{ dp[i-x][j-1] | i>=x }
ans=SUM{ dp[i][n]*(dp[i][n]-dp[i][n-1]) | 0<=i<=9*n }
前i位数字和为j里面具有前导零的方案<==>前i-1位数字和为j的方案  很巧妙

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<stdio.h>
 5 using namespace std;
 6 #define LL long long
 7 const LL mod = 1e9 + 7;
 8 LL dp[9005][2];
 9 int main()
10 {
11     register int  i, j, k ;
12     int len, m, cur = 0;
13     for (i = 0;i <= 9;++i) dp[i][cur] = 1;
14     scanf("%d", &len);
15     m = 9 * len;
16     for (j = 2;j <=len;++j)
17     {
18         cur ^= 1;
19         for (i = 0;i <= m;++i)
20         {
21             LL sum = 0;
22             for (int x = 0;x <= 9;++x) {
23                 if (i >=x) {
24                     sum =( sum + dp[i-x][cur^1]) ;
25                     if (sum > mod) sum %= mod;
26                 }
27                 else break;
28             }
29             dp[i][cur] = sum;
30         }
31     }
32     if (len == 1) { puts("9");return 0; }
33     LL ans = 0;
34     for (i = 0;i <= m;++i)
35         ans = (ans + dp[i][cur] * (dp[i][cur] - dp[i][cur^1])) % mod;
36     printf("%lld
", ans);
37     //system("pause");
38     return 0;
39 }