设为首页 加入收藏

TOP

[CTSC2017] 吉夫特
2019-06-11 00:07:53 】 浏览:32
Tags:CTSC2017 吉夫特

由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;
}

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C/C++語言 - 日常算法 - 蛇形填數 下一篇[HNOI/AHOI2018] 转盘