消失之物 bzoj-2287 Poj Challenge
题目大意：给定$n$个物品，第$i$个物品的权值为$W_i$。记$Count(x,i)$为第$i$个物品不允许使用的情况下拿到重量为$x$的方案数。
注释：$1\le n,val_i\le 2\cdot 10^3$。
想法：只需要用取模瞎**容斥一下就行了。
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2010
using namespace std;
int a[N],f[N],g[N];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
int main()
{
// freopen("thing.in","r",stdin);
// freopen("thing.out","w",stdout);
int n=rd(),m=rd(); for(int i=1;i<=n;i++) a[i]=rd();
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=a[i];j--) (f[j]+=f[j-a[i]])%=10;
}
for(int i=1;i<=n;i++)
{
memset(g,0,sizeof g);
g[0]=1;
for(int j=1;j<=m;j++)
{
printf("%d",((f[j]-g[j%a[i]])%10+10)%10);
g[j%a[i]]=((f[j]-g[j%a[i]])%10+10)%10;
}
puts("");
}
// fclose(stdin); fclose(stdout);
return 0;
}
小结：好题。