题解 P3773 【[CTSC2017]吉夫特】

# 广告 [这里观赏体验更佳](https://www.cnblogs.com/dedicatus545/p/9261490.html) # 思路 一句话题意： 给出一个长度为 n 的序列，求所有长度大于等于2的子序列个数，满足：对于子序列中任意两个相邻的数 a和 b （b 在 a 前面），$C_a^b mod 2=1$，答案对1e9+7取模 显然膜2余1是个非常特殊的性质，应当好好加以利用 和组合数取模有关的东西，有Lucas定理，因此我们来试着推一推 $C_n^m\;mod\;2=C_{n\;mod\;2}^{m\;mod\;2}\ast C_{n/2}^{m/2}$ 这个玩意的意义，显然就是把n和m转成二进制，那么只要没有某一位上n是0m是1（此时$C_0^1$无意义，视作0）就OK了 那么我们就把问题转化成了一个可以DP的问题 设dp[i]表示序列$[i,n]$中可能的种类数，那么可以通过枚举$a[i]$和哪些数满足上属性质 这个枚举过程可以巧妙地利用$j=(j+1)|a[i]$来完成，相当于是把$a[i]$的0一个个变成1 总效率不太会算，但是O(能过)还是有的 ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; inline ll read(){ ll re=0,flag=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') flag=-1; ch=getchar(); } while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar(); return re*flag; } ll MOD=1e9+7; ll n,a[300010],dp[300010],lim=233333; ll pl(ll a,ll b){ return (a+b>MOD)?a+b-MOD:a+b; } int main(){ n=read();ll i,j,ans=0; for(i=1;i<=n;i++) a[i]=read(); for(i=n;i>=1;i--){ for(j=a[i];j>=1;j=(a[i]&(j-1))){//注意枚举方法 dp[a[i]]=pl(dp[a[i]],dp[j]); } ans=pl(ans,dp[a[i]]); dp[a[i]]=pl(dp[a[i]],1); } printf("%I64d\n",ans); } ```