【BZOJ 4762】最小集合

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4762

吐槽

这题之前在绍一集训的时候就考过一次，今天又考了
但还是写炸了，或许老年选手不适合写代码吧！

解题报告

为了代码好写，我们先按照二进制位取反
这样的话，问题变为选出一些数，使其或起来为全集，且少一个都不行

我们考虑$f[i][j]$为将前$i$个数加入集合之后，或起来为$j$的方案数
这样可以防止一个数被之前的数代替，但对于之后的数却无能为力
于是我们加一维$f[i][j][k]$，其中$k$表示后面的数或起来为$k$

这样就可以使用类似容斥的思想进行两种转移

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$的系数

此时我们已经可以进行$O(n \cdot 4^{\omega})$的DP了
再仔细想想，第三维一定是第二维的子集，于是复杂度降到$O(n \cdot 3^{\omega})$

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];

inline int read() {
	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() {
	n = read();
	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;
}