首页 > 代码库 > 1043 幸运号码
1043 幸运号码
1043 幸运号码
基准时间限制：1 秒 空间限制：131072 KB 分值: 20
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。
dp[i][j]表示i个数组成的数字的和为j的方案数 ，这个需要两遍dp，一个有前导0，一个没有。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<math.h> 7 #include<set> 8 #include<vector> 9 #include<string.h>10 using namespace std;11 typedef long long LL;12 int dp[1005][10005];13 int dpp[1005][10005];14 const int mod = 1e9+7;15 int main(void)16 {17 int i,j,k,n;18 memset(dp,0,sizeof(dp));19 dp[0][0] = 1;20 scanf("%d",&n);21 for(i = 0; i < n; i++)22 {23 for(j = 0; j <= 10000 ; j++)24 {25 if(dp[i][j]==0)26 break;27 else {for(int s = 0; s <= 9; s++)28 {29 dp[i+1][s+j] = dp[i+1][s+j] + dp[i][j];30 dp[i+1][s+j]%=mod;31 }}32 }33 }34 memset(dpp,0,sizeof(dpp));35 dpp[0][0] = 1;36 for(i = 0; i < n; i++)37 {38 if(i==0)39 {40 for(j = 0; j <= 10000 ; j++)41 {42 if(dpp[i][j]==0)43 break;44 else {for(int s = 0; s <= 9; s++)45 {46 dpp[i+1][s+j] = dpp[i+1][s+j] + dpp[i][j];47 dpp[i+1][s+j]%=mod;48 }49 }}50 }51 else52 {53 for(j = 1; j <= 10000 ; j++)54 {55 if(dpp[i][j]==0)56 {57 break;58 }59 for(int s = 0; s <= 9; s++)60 {61 dpp[i+1][s+j] = dpp[i+1][s+j] + dpp[i][j];62 dpp[i+1][s+j]%=mod;63 }64 }65 }66 }67 LL sum = 0;68 for(i = 1; i <= 10000; i++)69 {70 if(dp[n][j] == 0)break;71 else72 {73 sum = sum + (LL)dp[n][i]*(LL)dpp[n][i]%mod;74 sum%=mod;75 }76 }77 printf("%lld\n",sum);78 return 0;79 }
1043 幸运号码
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。