1个长度为2N的数，如果左边N个数的和 = 右边N个数的和，那么就是一个幸运号码。
例如：99、1230、123312是幸运号码。
给出一个N，求长度为2N的幸运号码的数量。由于数量很大，输出数量 Mod 10^9 + 7的结果即可。
Input
输入N(1<= N <= 1000)
Output
输出幸运号码的数量 Mod 10^9 + 7
Input示例
1
Output示例
9
看的网上的题解 但是觉得他们写的还是有问题的
用dp[i][j]表示i个数的和为j的总数，这里面是包括0开头的情形，有dp[i][j]=dp[i-1][j-k](k从0到9)。
很好想，i个数组成总和为j的数量就来自于i-1个数 里面能 在最前面加0到9的数字使得加完之后和为j。
这里面包含了0开头的，把0去掉的方法就是dp[i][j]-dp[i-1][j]。
dp[i-1][j]就代表了在i个数中，开头为0的个数，减去就是i个数中开头不为0的个数。
原因很明显，i个数和为j与i-1个数和为j，就差了一个位置为0。而这一个位置因为一开始咱们的想法就是在最前面加的数字，所以这个位置就差在了最前面的位置上
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9+7; int dp[1010][10000];// dp[i][j] 为i个数 和为j的情况 int main() { int n; scanf("%d",&n); dp[0][0] = 1;//这里明明是网上题解有错误 他们都写的是dp[0][1] = 1 //明明他们是在凑样例的感觉 应该是0个数 凑成0的情况是1 for(int i=0;i<=9;i++) dp[1][i] = 1; for(int i=2;i<=n;i++) { for(int j=0;j<=9*i;j++) { int sum = 0; for(int k=0;k<=9;k++) { if(j >=k) sum = (sum + dp[i-1][j-k])%mod; else break; } dp[i][j] = sum; } } ll ans = 0; for(int i=0;i<=9*n;i++) ans = (ans + (ll)dp[n][i] * (dp[n][i]-dp[n-1][i]))%mod;//这里单独 (ll)dp[n][i] * (dp[n][i]-dp[n-1][i]) 会超精度 printf("%lld ",ans); }
下面是用滚动数组内存优化过的 用的now 和pre （强行装逼， 不过倒腾了半个小时 now 和 pre 的关系
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9+7; int dp[2][10000]; int main () { int n; scanf("%d",&n); int now = 0,pre = 1; dp[0][0] = 1; swap(now,pre); for(int i=0;i<=9;i++) dp[now][i] = 1; swap(now,pre); for(int i=2;i<=n;i++) { for(int j=0;j<=9*n;j++) { ll sum =0; for(int k=0;k<=9;k++) { if(j>=k) sum = (sum+dp[pre][j-k])%mod; else break; } dp[now][j] = sum; } swap(now,pre); } ll ans = 0; for(int i=0;i<=9*n;i++) { ans = (ans + (ll)dp[pre][i]*(dp[pre][i] - dp[now][i]))%mod; } printf("%lld ",ans); }
别人的代码 （随便看看就好 主要是滚动优化 可以学一下（n&1）
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define maxn 10005 #define Mod 1000000007 ll dp[2][maxn]; int main() { ll n,m,i,j,k,sum,ans=0; scanf("%lld",&n); dp[0][0]=1;//这里是0 for(i=0;i<=9;i++) dp[1][i]=1; for(i=2;i<=n;i++) { for(j=0;j<=n*9;j++) { sum=0; for(k=0;k<=9;k++) { if(j>=k) sum=(sum+dp[(i-1)%2][j-k])%Mod; else dp[i%2][j]=0; } dp[i%2][j]=sum; } } for(i=0;i<=9*n;i++) ans=(ans+dp[n%2][i]*(dp[n%2][i]-dp[(n-1)%2][i])%Mod)%Mod; printf("%lld ",ans); }