首先\(C(n,m)\)为奇数当且仅当\(n\&m=m\)。
简要证明: 因为是\(mod\ 2\)，考虑Lucas定理。
在\(mod\ 2\)的情况下\(C(n,m)\)最后只会化成4种情况：\(C(0,1),C(0,0),C(1,0),C(1,1)\)。 后三种情况都是1，\(C(0,1)\)不存在(=0)。所以如果\(C(n,m)mod\ 2\)为偶数，那么在Lucas的过程中一定出现了\(C(0,1)\)。\(mod\ 2\)的过程容易想到位运算。 由\(C(n,m)mod\ 2=C(n\%2,m\%2)*C(n/2,m/2)=C(n\&1,m\&1)*C(n>>1,m>>1)\) 可知，若\(C(n,m)\)为奇数，那么\(m\)一定是\(n\)二进制1的子集（否则存在\(C(0,1)\)）。
因为要满足\(n\&m=m\)，所以题意即为，有多少个\(a\)的子序列\(b\)，满足\(b_i\&b_{i+1}=b_{i+1}\)。
令\(f[i]\)表示以\(A[i]\)结尾的合法子序列数。 那么有两种显然的方式：- 枚举\(i\)，\(ans+=f[i]\)，再更新后面满足 \(A[j]\)的二进制位是\(A[i]\)二进制位的子集 的\(j\)，\(f[j]+=f[i]\)。
- 枚举\(i\)，枚举\(j\)，求\(f[i]=\sum_{j<i,A[j]是A[i]的超集}f[j]\)，然后\(ans+=f[i]\)。
两种都是枚举子集。第一种是不需要查询，转移\(O(3^{18})\)；第二种是查询\(O(3^{18})\)，不需要转移。
（整个算法实际上是对每个\(a_i\)的二进制表示枚举了它的子集，而\(a_i\)互不相同，相当于是对所有二进制子集枚举了它的子集，所以复杂度是\(3^{\log a_{max}}=3^{18}\)） 这样好像比较危险？（出二进制\(1\)很多的\(a_i\)）（以上都不是重点）
我们将这两种方式综合一下： 转移时，固定\(i\)的后\(9\)位，枚举\(i\)前\(9\)位的子集\(j\)，用\(f[i]\)更新后面的\(f[j]\)； 求值时，固定\(i\)的前\(9\)位，枚举\(i\)后\(9\)位的超集\(j\)，从前面的\(f[j]\)转移，即\(f[i]=\sum f[j]\)。这样复杂度是啥啊。。我不知道，反正靠谱很多。
顺便记下枚举子集复杂度\(O(3^n)\)的证明：
证明：设集合有\(n\)个元素，我们把所有子集\(s\)按元素个数\(k=|s|\)分类（因为它们的子集都为\(2^k\)个。那么枚举的集合数为：\[\sum_{k=0}^nC_{n}^k2^k=(1+2)^n=3^n\]
代码就是这样：
for(s=0; s
以前的题解（naive啊）：。
//3800kb 688ms#include#include #include //#define gc() getchar()#define MAXIN 2000000#define mod 1000000007#define Mod(x) x>=mod&&(x-=mod)typedef long long LL;const int N=(1<<18)+3,L=(1<<9)-1;struct io{ char IN[MAXIN],*s; io():s(IN) {IN[fread(IN,1,MAXIN,stdin)]=0;} inline operator int() { int x=0; for(; *s<48; ++s); for(; *s>47; x=x*10+*s++-48); return x; }}io;int main(){ static int f[N]; int n=io; LL ans=0,sum; for(int i=1,a; i<=n; ++i) { a=io,sum=0; int l=a&L, r=a>>9; for(int j=r; j<=L; j=(j+1)|r) sum+=f[(j<<9)|l]; ans+=sum%=mod, ++sum; r<<=9; for(int j=l; j; j=(j-1)&l) f[j|r]+=sum, Mod(f[j|r]); f[r]+=sum, Mod(f[r]);//0|r } printf("%lld\n",ans%mod); return 0;}