[luogu 3773][CTSC 2017]吉夫特

传送门

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<bits/stdc++.h>

#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 1000000007

int 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！

巴特西

[luogu 3773][CTSC 2017]吉夫特

传送门

Solution

最新文章

热门文章