- 定义一个集合是好的，当且仅当其中所有元素按位与的结果是(0)，且它的所有真子集按位与的结果都不是(0)。
- 给定一个大小为(n)的可重集，求它有多少好子集。
- (nle10^3,forall ale1024)
限制条件的巧妙转化
一个集合所有真子集按位与结果都不是(0)，显然等价于去掉任意一个元素之后按位与结果都不是(0)。
令(igwedge(S)=igwedge_{ain S}a)，(S/a)表示从(S)中删去(a)之后的集合，则我们可以把答案写成这个样子：
[ans=sum_S[igwedge(S)=0]wedge[forall ain S,igwedge(S/a)
ot=0]
]
对于后面这一项考虑容斥，于是原式就被转化为：
[ans=sum_S[igwedge(S)=0]wedgesum_{S'subseteq S}[forall ain S',igwedge(S/a)=0](-1)^{|S'|}
]
由于(forall ain S',igwedge(S/a)=0Leftrightarrow(igvee_{ain S'}igwedge(S/a))=0)，因此原式等同于：
[ans=sum_S[igwedge(S)=0]wedgesum_{S'subseteq S}[(igvee_{ain S'}igwedge(S/a))=0](-1)^{|S'|}
]
这个式子是由两个条件式([igwedge(S)=0],sum_{S'subseteq S}[(igvee_{ain S'}igwedge(S/a))=0])以及一个权值((-1)^{|S'|})组成的。
因此考虑把前两个条件式中的值值放在状态里，把权值记在(DP)值中。
于是设(f_{i,j,k})表示做完前(i)个数，(j=igvee_{ain S'}igwedge(S/a),k=igwedge(S))时((-1)^{|S'|})的和。
那么转移无非三种，分别就是既不在(S)也不在(S')，只在(S)，既在(S)又在(S')，转移方程应该还是容易推的，也可以直接看代码。
具体实现中需要滚存，由于(k)必然是(j)的子集，所以(j,k)的总状态数并非(2^{20})，而是(3^{10}).
代码：(O(n imes3^{10}))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000
#define V 1023
#define X 1000000007
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int n,g[V+5],f[2][V+5][V+5];
int main()
{
RI i,j,k;for(g[0]=X-1,i=1;i<=V;++i) g[i]=(i&1?X-1LL:1LL)*g[i>>1]%X;//g[i]=(-1)^|i|
RI x,t;for(scanf("%d",&n),f[0][V][V]=i=1;i<=n;++i)//初始化j,k都为全集
{
for(scanf("%d",&x),j=0;j<=V;++j) for(k=j;;k=(k-1)&j) if(f[i&1][j][k]=0,!k) break;//清空
for(j=0;j<=V;++j) for(k=j;;k=(k-1)&j) if((t=f[i&1^1][j][k])&&//转移
(Inc(f[i&1][j][k],t),Inc(f[i&1][j&x][k&x],t),Inc(f[i&1][j&x|k][k&x],X-t)),!k) break;//分三类
}return printf("%d
",f[n&1][0][0]),0;//最终要求j=k=0
}