看了题解才发现loj上面的题面漏了一小部分……uoj上的题面是完整的.
由Lucas定理易知$\binom{n}{m}\equiv 1\pmod{2}\leftrightarrow m\subset n$.
让$f _{i,j}$表示从$i$位置或$i$位置之后开始的，所有数都包含于$j$的子序列的方案数，转移显然.$i$那一维可以直接滚动，因为题目保证输入的数互不相同，所以复杂度不会超过枚举子集的复杂度，即$\mathcal O(3^{\log _2a})$，也就是$\mathcal O(a^{\log _23})$.
辣鸡bzoj就非得要我把取模改成减法卡卡常数才让我过……
代码：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
using namespace std;
ele n,mx,a[maxn],f[maxa],g[maxa];
inline ele add(ele x,ele y){
return (x+y>=MOD)?x+y-MOD:x+y;
}
int main(){
scanf("%d",&n);
for (int i=0; i<n; ++i) scanf("%d",a+i),mx=max(mx,a[i]);
memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
for (int i=n-1; ~i; --i){
ele tmp=0;
for (int s=a[i]; s; s=(s-1)&a[i])
tmp=add(tmp,add(f[s],g[s]));
f[a[i]]=add(f[a[i]],tmp);
++g[a[i]];
}
ele ans=0;
for (int i=0; i<=mx; ++i) ans=add(ans,f[i]);
printf("%d\n",ans);
return 0;
}