思路： 先处理出来f[j]表示这i个物品都可用 填满容量j的方案数
容斥一发
处理出来g[j]=g[j-w[i]] 表示i不能用的时候 填满容量j的方案数
//By SiriusRen#include <cstdio>using namespace std;int n,m,w[2005],f[2005],g[2005];int main(){ scanf("%d%d",&n,&m),f[0]=1; for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) f[j]=(f[j]+f[j-w[i]])%10; for(int i=1;i<=n;i++){ for(int j=0;j<w[i];j++)g[j]=f[j]; for(int j=w[i];j<=m;j++)g[j]=((f[j]-g[j-w[i]])%10+10)%10; for(int j=1;j<=m;j++)PRintf("%d",g[j]); puts(""); }}
新闻热点
疑难解答
