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的方案  很巧妙

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<stdio.h>

 using namespace std;

 #define LL long long

 const LL mod = 1e9 + ;

 LL dp[][];

 int main()

 {

     register int  i, j, k ;

     int len, m, cur = ;

     for (i = ;i <= ;++i) dp[i][cur] = ;

     scanf("%d", &len);

     m =  * len;

     for (j = ;j <=len;++j)

     {

         cur ^= ;

         for (i = ;i <= m;++i)

         {

             LL sum = ;

             for (int x = ;x <= ;++x) {

                 if (i >=x) {

                     sum =( sum + dp[i-x][cur^]) ;

                     if (sum > mod) sum %= mod;

                 }

                 else break;

             }

             dp[i][cur] = sum;

         }

     }

     if (len == ) { puts("");return ; }

     LL ans = ;

     for (i = ;i <= m;++i)

         ans = (ans + dp[i][cur] * (dp[i][cur] - dp[i][cur^])) % mod;

     printf("%lld\n", ans);

     //system("pause");

     return ;

 }

巴特西

51nod 1043 数位dp

最新文章

热门文章