消失之物 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;
- }
小结: 好题.
[bzoj2287][poj Challenge] 消失之物_背包 dp_容斥原理
来源: http://www.bubuko.com/infodetail-2879073.html