[51nod1043]幸运号码

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

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

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

解题关键：

动态规划，dp[i][j]表示i个数和为j的总数（这里包括开头为0的情况）

$dp[i][j] = \sum\limits_{k = 0}^9 {dp[i - 1][j - k]} $
最后，我们只需要用去掉0打头的情况*没有去掉0打头的情况累加并取模即可。
这里去掉0的方法是$dp[n][i] - dp[n - 1][i]$

为什么是这样呢？因为只要第一位为0，不论后面的是否为0，都无影响，所以第一位确定，处理后面的n-1位即可。

这里可以进行滚动数组优化。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=1e9+;

ll dp[][];

int main(){

    int n;

    cin>>n;

    dp[][]=;

    for(int i=;i<=n;i++){

        for(int j=;j<=*i;j++){

            for(int k=;k<=&&k<=j;k++){

                dp[i][j]+=dp[i-][j-k];

                dp[i][j]%=mod;

            }

        }

    }

    ll ans=;

    for(int i=;i<=*n;i++){

        ans+=dp[n][i]*(dp[n][i]-dp[n-][i]);

        ans%=mod;

    }

    cout<<ans<<"\n";

    return ;

}

巴特西

[51nod1043]幸运号码

最新文章

热门文章