bzoj 4762 最小集合

Posted on | Views:

状压 $dp$ .

  • 如果把所有元素 $xor\ 1023$ ,那么就等价于集合内元素 $or$ 和为 $1023$ ,去掉任意一个后 $or$ 和不为 $1023$ .
  • 设 $f(i,j,k)$ 表示考虑了前 $i$ 个数,前面已经选择的数 $or$ 和为 $j$ ,期望后面选出的数 $or$ 和包含 $k$ 时的方案数.
  • 若第 $i+1$ 个数为 $x$ ,不选它,则有 $f(i+1,j,k)+=f(i,j,k)$ .
  • 如果选了它,假设能转移到 $f(i+1,j|x,k’)$ ,那么 $k’$ 需要满足:
  1. $k’|x=k$ .
  2. $k’|j|x\not= k’|j$ .这是为了保证去掉 $x$ 后就不合法了.
  • 如果只考虑满足第一个条件的,就有 $f(i+1,j|x,k\ xor\ (k\&x) )+=f(i,j,k)$ .因为 $x,k$ 都为 $1$ 的位置上可以随便选.
  • 还要减去满足第一个条件,但不满足第二个条件的部分. $f(i+1,j|x,(k\ xor\ (k\&x))|(x\ xor (x\& j)) )-=f(i,j,k)$ .
  • 后面括号表示 $x$ 对 $j$ 产生的贡献,即将原来的 $0$ 变为了 $1$ .如果 $k’$ 的这些位上也是 $1$ ,就不满足第二个条件了.
  • 初始有 $f(0,0,0)=1$ ,答案为 $f(n,1023,0)$ .这样做是 $O(n\cdot 4^{10})$ 的.
  • 注意到若 $f(i,j,k)\not = 0$ ,则一定有 $k$ 是 $j$ 的子集.于是枚举 $k$ 时只用枚举 $j$ 的子集.时间复杂度 $O(n\cdot 3^{10})$ .

滚掉第一维,优化空间.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
inline int add(int a,int b)
{
	return (a + b >= P)? (a + b - P) : (a + b); 
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int N=1023;
int n,a[N+10],f[2][N+10][N+10];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read()^N;
	int id=0;
	f[0][0][0]=1;
	for(int i=1;i<=n;++i)
	{
		int x=a[i];
		memset(f[id^1],0,sizeof f[id^1]);
		for(int j=0;j<=N;++j)
		{
			for(int k=j;;k=(k-1)&j)
			{
				if(f[id][j][k])
				{
					f[id^1][j][k]=add(f[id^1][j][k],f[id][j][k]);
					f[id^1][j|x][k^(k&x)]=add(f[id^1][j|x][k^(k&x)],f[id][j][k]);
					f[id^1][j|x][(k^(k&x))|(x^(x&j))]=add(f[id^1][j|x][(k^(k&x))|(x^(x&j))],P-f[id][j][k]);
				}
				if(!k)
					break;
			}
		}
		id^=1;
	}
	cout<<f[id][N][0]<<endl;
	return 0;
}