UOJ300吉夫特

2019-04-13 12:35发布

站内文章 / 模拟电子
14979 0 1209
传送门
我真是智障，明明知道Lucas定理，却不知道
(nm)≡1(modn)等价于(n2m2)∗(n模2的余数m模2的余数)≡1(modn)
然后(n模2的余数m模2的余数)不等于零，等价于二进制下，n的末位大于等于m。再结合(n2m2)，可以推知(nm)≡1(modn)等价于n&m==m。
设s为值域（等于ai的最大值）
然后我看漏了所以ai都互不相等，作死写了个O(n∗s12)按前9位暴力，后九位前缀和的分块做法。实际上，因为ai互不相等，所以暴力枚举子集是O(3(log2s))（其中s是为O(n)），约为O(n∗s0.581) #include typedef long long ll; const int N=300000; const ll mo=1000000007; int n,i,f[N],j,g[N],a[N],ans,x,y,s[513][513],all=(1<<9)-1; int main(){ //freopen("ex_gift9.in","r",stdin); scanf("%d",&n); for(i=1;i>>1]+(i>>1); for(i=1;i<=n;++i)scanf("%d",a+i); for(i=1;i<=n;++i){ for(x=a[i]>>9,y=a[i]&all,j=all^x;;j=(j-1)&(all^x)){ g[i]=(s[all^j][y]+g[i])%mo; if(!j)break; } ans=(ans+g[i])%mo; g[i]=(g[i]+1)%mo; for(j=y;;j=(j-1)&y){ s[x][j]=(s[x][j]+g[i])%mo; if(!j)break; } } printf("%d ",ans); return 0; }

热门文章