[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; }
上一篇: 古龙妙语论男女
下一篇: 读书人比不读书人聪明