# 【BZOJ 4762】最小集合

### 解题报告

1. $f[i][j][k] \to f[i+1][j|a_i][k-(k \& a_i)]$表示不强制非法
2. $-f[i][j][k] \to f[i+1][j|a_i][(k-(k \& a_i))|(a_i-(a_i \& j))]$表示强制非法
ps: 根据容斥原理，第二种转移会配上$-1$的系数

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1001;
const int M = (1 << 10) - 1;
const int MOD = 1000000007;

int n,vout,a[N],f[1<<10][1<<10];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
for (int i=1;i<=n;i++) a[i] = read() ^ M;
f[0][0] = 1;
for (int t=1;t<=n;t++) {
for (int i=M,ti,tj,uni;~i;--i) {
if ((ti = (a[t] | i)) > i) {
uni = ti - i;
for (int j=i;;(--j)&=i) {
tj = (j - (j & a[t]));
f[ti][tj] = (f[ti][tj] + f[i][j]) % MOD;
f[ti][tj|uni] = (f[ti][tj|uni] - f[i][j]) % MOD;
if (!j) break;
}
}
}
}
printf("%d\n",(f[M][0]+MOD)%MOD);
return 0;
}


## 2 thoughts to “【BZOJ 4762】最小集合”

1. WONDERFUL Post.thanks for share..extra wait .. …

2. Howdy just wanted to give you a brief heads up and let you know a few of the pictures aren’t loading correctly. I’m not sure why but I think its a linking issue. I’ve tried it in two different internet browsers and both show the same results.