欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[CTSC2017] 吉夫特

程序员文章站 2022-04-08 14:50:35
由Lucas定理,C(n,m)%P=C(n%p,m%p) C(n/p,m/p)可知C(n,m)为奇数的充要条件是(n&m)=m。 考虑到ai using namespace std; const int N=233335; const int mod=1000000007; int n,a[N],p ......

由lucas定理,c(n,m)%p=c(n%p,m%p)*c(n/p,m/p)可知c(n,m)为奇数的充要条件是(n&m)=m。

考虑到ai<=233333,可以开桶优化dp(笑。这样的总转移次数=σi的子集数=3^log2。

#include <bits/stdc++.h>
using namespace std;
const int n=233335;
const int mod=1000000007;

int n,a[n],p[n],f[n];

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) {
        scanf("%d",a+i);
        f[a[i]]=1;
        p[a[i]]=i;
    }
    for(int i=1; i<=n; ++i) {
        for(int j=a[i]; j; j=(j-1)&a[i]) {
            if(p[j]>i) (f[j]+=f[a[i]])%=mod;
        }
    }
    int s=0;
    for(int i=1; i<=n; ++i) (s+=f[a[i]]-1)%=mod;
    printf("%d\n",(s+mod)%mod);
    return 0;
}