感谢度教。。。
转化条件1 : 使得Or集为全集 其他不变
一个合法集合S必不存在一个大小为|S|−1的子集T满足条件1 即一个集合合法必不存在一对长度和小于|S|的前缀与后缀使得Or集为全集
然后考虑暴力 g[i][j][k]表示已经做了前i个 当前Or和为j 之后Or和期望为k时的方案数
转移时并不好处理
考虑改一下状态 f[i][j][k]表示已经做了前i个 当前Or和为j 之后Or和期望包含k时的方案数 g[0][0][1023]=1 则转移很方便 有 f[i][j][k]−>g[i+1][j|a[i+1]][l] S∈l && l∈T && l≠T S=k&−a[i+1] T=S|(a[i+1]&−j) f即为g的子集和 发现可以直接利用 f 进行转移 f[i 1][j|a[i 1]][S] =f[i][j][k] f[i+1][j|a[i+1]][T]−=f[i][j][k] 时间复杂度 O(n∗410)
发现最后的答案 f[n][1023][0] 只和 g[0][0][1023] 有关 所以我们可以直接令 f[0][0][0]=1 做出来答案不变
这有什么好呢？ 我们会发现所有有用的集合k皆为j的子集
然后就变成了 O(n∗310)
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; int f[2][1024][1024]; const int Mod=1e9+7; inline void Up(int&a,int b){a+=b;a>=Mod?a-=Mod:(a<0?a+=Mod:a);} int main() { int n; scanf("%d",&n); int now=1,last=0; f[last][0][0]=1; for(int i=1;i<=n;i++,now^=1,last^=1) { int p,t; scanf("%d",&p); for(int j=0;j<1024;j++) for(int k=j;;k=(--k)&j) { f[now][j][k]=f[last][j][k]; if(!k)break; } p=1023-(t=p); for(int j=0;j<1024;j++) if((j|p)^j) for(int k=j;;k=(--k)&j) { Up(f[now][j|p][k&t],f[last][j][k]),Up(f[now][j|p][(k&t)|(p^(p&j))],-f[last][j][k]); if(!k)break; } } cout<<f[last][1023][0]; return 0; }