解题思路：B君出的题，不可做 如何判断组合数是否是奇数？ 首先， Ckn=n!k!(n−k)! C n k = n ! k ! ( n − k ) ! ，假设 n! n ! 的2因子数为 a a ，k!k!的2因子数是 b b ，(n−k)!(n−k)!的2因子数为 c c ，那么如果CknCnk是奇数，则 a=b+c a = b + c 怎么求出 x! x ! 的2因子个数呢？首先我们可以将x除以2，相当于一个提取公因数的过程，而那些不能被2整除的项就会被丢掉，于是剩下来的是 2∗(x2!) 2 ∗ ( x 2 ! ) ，一直这样处理下去，得到答案为
f(x)=∑i=1∞x2i f ( x ) = ∑ i = 1 ∞ x 2 i 我们设 g(x)=x g ( x ) = x ，那么 g(x)=g(x2)+x2+(xmod2)=∑∞i=1x2i+ g ( x ) = g ( x 2 ) + x 2 + ( x mod 2 ) = ∑ i = 1 ∞ x 2 i + (x在二进制下1的个数） 所以 x! x ! 的2因子个数就是(x-x在二进制下1的个数) 那么 Ckn C n k 是奇数的条件即为：n在二进制下1的个数=k在二进制下1的个数+(n-k)在二进制下1的个数。 假设二进制下，n拥有的某一个1，k并没有，那么： n: …0… k: …1… n-k: …11…. 会发现k和(n-k)二进制下1的个数和一定会大于n，所以必须k所有的1 n都拥有才能符合条件，综上， Ckn C n k 是奇数的条件为： (n&k)=k 那么后面的事情就简单了，设 fi f i 表示以 ai a i 开头的子序列个数，用桶存每一个 ai a i 出现的位置 i i 。计算fifi时，考虑下一个放什么，也就是枚举 ai a i 的子集，判断这个数是否在 i i 后面，然后统计方案即可。 复杂度是O(3logmaxa)O(3logmaxa)的 #include<bits/stdc++.h> using namespace std; #define RI register int int read() { int q=0;char ch=' '; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar(); return q; } const int N=240000,mod=1000000007; int a[N],T[N],f[N]; int n,ans; int qm(int x) {return x>=mod?x-mod:x;} int main() { n=read(); for(RI i=1;i<=n;++i) a[i]=read(),T[a[i]]=i; for(RI i=n;i>=1;--i) { f[i]=1; for(RI j=a[i]&(a[i]-1);j;j=a[i]&(j-1)) if(T[j]>i) f[i]=qm(f[i]+f[T[j]]); ans=qm(ans+f[i]); } ans=(ans-n+mod)%mod; printf("%d\n",ans); return 0; }