51nod 1043

灰太狼 2022-08-21 03:14 177阅读 0赞

题意：

求在2\*n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=1000

分析：

数位dp题目，这道题目想了很久，刚开始以为是dp\[i\]\[j\] 表示的是前 i 位数字和后 i 位数字的差为 j  ，是这样的。结果递推方程想了很久也没有一个统一的结果，需要一个一个的来推，倒是大概好像有一个统一的想法，可是一直没有成型。

后来查了一个才知道思路错了，根本不是这样的。

其实是这样的，我们用dp\[i\]\[j\]表示的是前i位的数字和为j，j最大为9\*i  ，前i位每位都是9的时候。   这样假如我们求得了dp\[n\]\[1\]一直到dp\[n\]\[9\*n\]的数字，那么最终结果就是dp\[n\]\[1\] \* dp\[n\]\[1\]  +   ... + dp\[n\]\[9\*n\] \* dp\[n\]\[9\*n\]  .  但是这里还有一个问题就是，dp\[i\]\[j\] 表示的是前i位的数字和为j，但是我们知道前面的那个 i位 是 不能有前置0的，所以还有处理一下。其实可以看到，没有前置0的结果是 dp\[i\]\[j\] - dp\[i-1\]\[j\] ,  因为每次都是在前面加数字，所以要是i位和i-1位的和一样，就是前置0的数字了。

接下来就是怎么求解dp\[i\]\[j\] 了, dp\[i\]\[j\]    +=    dp\[i-1\]\[j-k\]  ;  (j>=k,k=0,1,2...9)  .很好理解 。

#include <map>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std ;
    #define mem(a) memset(a,0,sizeof(a))
    #define mod 1000000007
    
    int const maxn = 1005;
    long long dp[2][maxn*9];
    //dp[i][j]表示的是i位数字并且这i位数字的和为j的个数，这里没有考虑前置0
    //这里有了一个优化，直接用的是dp[2][maxn*2]，因为递推的话i位数字的和只与i-1位的数字有关系
    //所以这里直接每次只记录i-1和i位数字的和就可以了。
    
    int main()
    {
        int n ;
        while(scanf("%d",&n)!=EOF)
        {
            mem(dp);
            dp[0][0]=dp[1][0] = 1 ; //初始化，和为0只有一种情况
            for(int i = 1 ; i <= 9 ; i++) dp[0][i] = 1 ;
            for(int i = 1 ; i < n ; i++)
            {
                for(int j = 0 ; j <= (i+1)*9 ; j++)
                {
                    long long sum = 0 ;
                    for(int k = 0 ; k <= 9 ; k++)
                    {
                        if(j>=k)
                        {
                            //第i位的数字为k就可以了
                            sum=(sum+dp[(i-1)%2][j-k])%mod;
                        }
                    }
                    dp[i%2][j] = sum ;
                }
            }
            long long ans = 0 ;
            for(int i = 0 ; i <= n*9 ; i++)
            {
                ans = (ans + dp[(n+1)%2][i] * (dp[(n+1)%2][i] - dp[n%2][i])) % mod ;
            }
            printf("%I64d\n",ans);
        }
        return 0 ;
    }