注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3823]定情信物  

2015-04-01 11:05:45|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3823: 定情信物

#include<cstdio>
#include<cstdlib>
using namespace std;
const int N = 1E7+100;
typedef long long ll;
int n,MOD;
int inv[N],sinv[N],sum[N];
inline int kpow(int x,int k){
int re=1;
for(;k;k/=2,x=(ll)x*x%MOD)
if(k&1)re=(ll)re*x%MOD;
return re;
}
int main(){
//printf("%lf\n",sizeof(inv)*4./1024/1024);
int i, j;
scanf("%d%d",&n,&MOD);
if(n==1){printf("%d\n",1%MOD);return 0;}
// getpri();
int ans = 0,two=1,mul=1,tmp;
inv[1] = 1;
sinv[0] = sinv[1] = 1;
for(i=2;i<=n;i++){

tmp = 0;
if(i%MOD != 0){
if(i > MOD) inv[i] = inv[i%MOD];
else inv[i] = (ll)-(MOD / i) * inv[MOD % i] %MOD;
mul = (ll)mul*i%MOD;
}else{
j = i;
while(j%MOD==0){
j/=MOD;
tmp++;
}
inv[i] = inv[j%MOD];
mul = (ll)mul*j%MOD;
}
sinv[i] = (ll)inv[i] * sinv[i-1]%MOD;
sum[i] = sum[i-1] + tmp;
}
// for(i=0;i<=n;i++)printf("%d ",inv[i]);printf("\n");
// for(i=0;i<=n;i++)printf("%d ",sinv[i]);printf("\n");
// for(i=0;i<=n;i++)printf("%d ",sum[i]);printf("\n");
for(i=n;i>=0;i--){
tmp = (ll)mul*sinv[i] %MOD
* sinv[n-i] %MOD
* two %MOD
* kpow(MOD,sum[n] - sum[i] - sum[n-i])%MOD;
if(tmp < 0)tmp += MOD;
ans ^= tmp;
//printf("%d\n",tmp);
two = two*2;if(two >= MOD)two-=MOD;
}
printf("%d\n",ans);
return 0;
}

题解:
数论
设f[i][j]为i维超立方体j维元素数
发现f[i][j]/f[i-j][0] = C(i,j) , f[i-j][0] = 2^(i-j)
然后就可以做了……
线性逆元 inv[i] = -( MOD/i ) * inv[MOD%i] %MOD
坑点:
MOD <= n
如果 i%MOD == 0 就把MOD这个质因子提出来分开处理就好了
gcd( i,MOD )= 1, i>MOD inv[i] = inv[i%MOD]
  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017