怎么求出$x!$的2因子个数呢?首先我们可以将x除以2,相当于一个提取公因数的过程,而那些不能被2整除的项就会被丢掉,于是剩下来的是$2*(\frac{x}{2}!)$,一直这样处理下去,得到答案为
那么$C_n^k$是奇数的条件即为:n在二进制下1的个数=k在二进制下1的个数+(n-k)在二进制下1的个数.
假设二进制下,n拥有的某一个1,k并没有,那么:
会发现k和(n-k)二进制下1的个数和一定会大于n,所以必须k所有的1 n都拥有才能符合条件,综上,$C_n^k$是奇数的条件为:(n&k)=k
那么后面的事情就简单了,设$f_i$表示以$a_i$开头的子序列个数,用桶存每一个$a_i$出现的位置$i$.计算$f_i$时,考虑下一个放什么,也就是枚举$a_i$的子集,判断这个数是否在$i$后面,然后统计方案即可.