枚举子集
发现自己经常记不住这个怎么写，就来写篇题解吧。
首先对于一个 \(n\) 位二进制数 \(x\)，求二进制位上都是 \(x\) 的子集的数有哪些，
比如：101的子集有100、001、000。
然后这个东西如果直接 \(2^n\) 次枚举的话，复杂度就爆炸了。
所以可以用一个很厉害的东西，
代码长这样：
for(int i=(x-1)&x;i;i=(i-1)&x)
这个 \(i\) 直接就是枚举出来的子集了。
这个为啥是对的呢？
我的理解是，你普通枚举 \(i\)-- 了之后，可能出现一个地方 \(i\) 有个 \(1\) 但是 \(x\) 是 \(0\)。
所以你把 \(i\) 和 \(x\) 与一下，来把这个 \(1\) 消掉就好了。
如果只求一个 \(x\) 的所有子集，那复杂度就是 \(2^n\)。
但是如果求 \(1\sim 2^n-1\) 中的数字的所有子集，那这个的复杂度就是 \(3^n\)。
（好像是用什么二项式定理求出来的，但是蒟蒻不会qwq）
例题
P3773 [CTSC2017] 吉夫特
发现组合数可以用 \(lucas\) 分解一下，相当于对于 \(2\le i \le k\) ，\(a_{b_i}\) 都要是 \(a_{b_{i-1}}\) 二进制位上的子集。
直接 \(dp\)，设 \(f[i]\) 表示以 \(i\) 结尾的合法子序列个数。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,mod=1e9+7;
int n,ans,f[N];
int main()
{scanf("%d",&n);for(int i=1,x;i<=n;i++){scanf("%d",&x);for(int j=(x-1)&x;j;j=(j-1)&x)f[j]=(f[j]+f[x]+1)%mod;ans=(ans+f[x])%mod;}printf("%d",ans);return 0;
}