题解 P3773 【[CTSC2017]吉夫特】
litble
2018-05-02 21:58:17
[~~点击就送屠龙刀~~ 个人博客安利](https://blog.csdn.net/litble/article/details/80172715)
~~解题思路：B君出的题，不可做~~
**如何判断组合数是否是奇数？**
首先，$C_n^k=\frac{n!}{k!(n-k)!}$，假设$n!$的2因子数为$a$，$k!$的2因子数是$b$，$(n-k)!$的2因子数为$c$，那么如果$C_n^k$是奇数，则$a=b+c$
怎么求出$x!$的2因子个数呢？首先我们可以将x除以2，相当于一个提取公因数的过程，而那些不能被2整除的项就会被丢掉，于是剩下来的是$2*(\frac{x}{2}!)$，一直这样处理下去，得到答案为
$$f(x)=\sum_{i=1}^{ \infty} \frac{x}{2^i}$$
我们设$g(x)=x$，那么$g(x)=g(\frac{x}{2})+\frac{x}{2}+(x\bmod 2)=\sum_{i=1}^{ \infty} \frac{x}{2^i}+$(x在二进制下1的个数）
所以$x!$的2因子个数就是(x-x在二进制下1的个数)
那么$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都拥有才能符合条件，综上，$C_n^k$是奇数的条件为：`(n&k)=k`
那么后面的事情就简单了，设$f_i$表示以$a_i$开头的子序列个数，用桶存每一个$a_i$出现的位置$i$。计算$f_i$时，考虑下一个放什么，也就是枚举$a_i$的子集，判断这个数是否在$i$后面，然后统计方案即可。
复杂度是$O(3^{\log maxa})$的
```cpp
#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;
}
```