Solution

输入一个长度为n的数列，求有多少个长度大等于2的不上升子序列满足：

\[\prod_{i=2}^{k} C(a_{b_{i-1}},a_{b_i}) mod\ 2 >0 \]

答案对1e9+7取模

根据Lucas定理：

\[C\ (n,\ m)\ ≡\ C\ (\frac{n}{p},\frac{m}{p})*\ C\ (n\%p,\ m\%p)\ (mod\ p)\]

可以发现，只要满足m是n的子集，或者说是(n&m)=m即可。

令f[i]表示从\(a_i\)开始的序列的数量，转移时枚举 \(a_i\)的子集，要判断一下它出现的位置是否在i之后

因为我们的\(a_i\)时互不相同的，所以，复杂度大概是\(O(3^{\log \max a_i})\)

写博客的真实原因其实是，pac弱到连枚举子集都不会

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define swap(x,y) (x^=y^=x^=y)inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 211990#define MM 233335#define mod 1000000007int a[MN],pos[MM],f[MN];int n,ans;inline void add(int &x,int y){x+=y;x>=mod?x-=mod:0;}int main(){    n=read();    register int i,j;    for(i=1;i<=n;++i) a[i]=read(),pos[a[i]]=i;    for(i=n;i;--i)    {        f[i]=1;        for(j=a[i]&(a[i]-1);j;j=a[i]&(j-1))            if(pos[j]>i) add(f[i],f[pos[j]]);        add(ans,f[i]);    }    add(ans,mod-n);    printf("%d\n",ans);    return 0;}
    

所以呢，如何枚举子集？

for(i=S;i&=S;--i)

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！