首页 > 代码库 > AC日记——幸运号码 51nod 1043
AC日记——幸运号码 51nod 1043
幸运号码
思路：
传说中的数位dp；
不难发现，n(n<1000) ，那么，n个数的最大和为9*1000=9000；
对于9000*1000的时间范围，我们可以用dp来解决；
dp[i][j]，表示第i为数总和为j的号码的个数；
每个dp[i][j]都是dp[i-1][j-v](0<=v<=9) 的总和；
然后按照左边的n和右边的n，分为有前导0，和没有前导0进行dp；
然后输出排列的答案即可；
dp[1000][9000]*2会爆空间，所以我选择压掉i维；
来，上代码：
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;#define ri 9005#define mod 1000000007long long n,dp[9005],ans,f[9005];int main(){ scanf("%d",&n),f[0]=1; for(int i=1;i<=9;i++) dp[i]=1,f[i]=1; for(int i=2;i<=n;i++) { for(int j=9*n;j>=1;j--) { long long dpos=0,fpos=0; for(int v=0;v<=9;v++) { if(j-v>=0) { fpos=(fpos+f[j-v])%mod; dpos=(dp[j-v]+dpos)%mod; } else break; } f[j]=fpos,dp[j]=dpos; } } for(int i=1;i<=9*n;i++) ans=(ans+(dp[i]*f[i])%mod)%mod; cout<<ans; return 0;}
AC日记——幸运号码 51nod 1043
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。