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示例
1
Output示例
9
#include<bits/stdc++.h>
#define cle(n) memset(n,0,sizeof(n))
using namespace std;
typedef long long ll;
const ll inf =1e18;
const int maxn = 1000100;
const int mod = 1000000007;
int n;
ll dp[2][9*1005];
int main()
{
cin>>n;
cle(dp);
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=9*i;j++)
{
dp[i&1][j]=0;
for(int k=0;k<=9;k++)
{
if(j<k)continue;
dp[i&1][j]=(dp[i&1][j]+dp[(i-1)&1][j-k])%mod;
}
}
}
ll ans=0;
for(int i=0;i<=n*9;i++)
ans=(ans+dp[n&1][i]*(dp[n&1][i]-dp[(n-1)&1][i]))%mod;
cout<<ans<<endl;
}
