首页 > 代码库 > CodeForces 213B Numbers
CodeForces 213B Numbers
$dp$，组合数。
$dp[i][j]$表示只用数字$i$,$i+1$,$i+2$......,$9$，凑成长度为$j$的并且数字$i$到$9$符合要求的方案数。只要枚举数字$i$用几个就可以转移了。
$dp[i][j] = \sum\limits_{k = a[i]}^n {(dp[i + 1][j - k]} *c[j][k])$，$0$的时候需要特别写一下转移方程，因为$0$不能放在第一位。
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;int n,a[15],sum[15];long long c[110][110],dp[15][110];long long mod=1e9+7;int main(){ for(int i=0;i<=100;i++) c[i][0]=c[i][i]=1; for(int i=1;i<=100;i++) { for(int j=1;j<i;j++) { c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } } scanf("%d",&n); for(int i=0;i<=9;i++) scanf("%d",&a[i]); memset(dp,0,sizeof dp); for(int i=a[9];i<=n;i++) dp[9][i]=1; for(int i=8;i>=0;i--) { sum[i]=sum[i+1]+a[i]; for(int j=sum[i];j<=n;j++) { for(int k=a[i];k<=j;k++) { if(i!=0) dp[i][j]=(dp[i][j]+dp[i+1][j-k]*c[j][k]%mod)%mod; else { if(j-1>=0) dp[i][j]=(dp[i][j]+dp[i+1][j-k]*c[j-1][k]%mod)%mod; } } } }/* for(int i=9;i>=0;i--) { cout<<"---- "<<i<<"----"; for(int j=0;j<=n;j++) { cout<<dp[i][j]<<"*"; } cout<<endl; }*/ long long ans=0; for(int i=1;i<=n;i++) ans=(ans+dp[0][i])%mod; printf("%lld\n",ans); return 0;}
CodeForces 213B Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。