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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4869 Turn the pokers  

2014-07-23 18:29:32|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4869
多校合练第一场第9题。
题意:桌上有m张人面朝下的纸牌,依次翻牌n次,每次翻ai张牌,问最后有多少种不同结果,结果对1000000009取余。
题解:
如果能够确定最后牌序列中有多少张朝上的(朝上记为1,朝下记为0),那么结果就是sigma(c(m,k))%mod,k是1的个数。通过简单模拟下,可以确定的是,最后1的个数的奇偶性和总翻牌次数的奇偶性是一样的,而且1的个数落于某个区间[a,b]内,每间隔2个可以取到(由奇偶性可以得出)。所以只要求出上界mn和下界mx即可。
最后求sigma(c(m,k)),可以用两种方法求解:因为n和m数据范围在10^5内,所以可以用lucas定理求解c(m,k)%mod;另外也可以用公式
c(m,i)=(c(m,i-1)*(m-i+1)/i)%mod
         =(c(m,i-1)*(m-i+1)*(i^(mod-2)))%mod //乘法逆元
打表求出前mx项的c(m,i)%mod,然后求和即可。

打表求解:

int n,m,x;
LL f[N];

LL mod_exp(LL a,LL b,LL c)
{
LL ans=1;
while(b)
{
if(b & 1)
ans=ans*a%c;
a=a*a%c;
b/=2;
}
return ans;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
while(sf2(n,m)!=EOF)
{
int p,mn=0,mx=0;
fr(n){
sf(x);
//update mn
if(x <= mn) p=mn-x; //如果x在区间左边,mn-=x
else if(x <= mx) p=(x%2 == mn%2)?0:1; //如果在区间范围内,那么mn可以达到0或1,由x和mn的奇偶性决定结果是0或1
else p=x-mx; //否则mn为x-mx可以得到最小

//update mx
if(mx+x <= m) mx=mx+x; //如果mx+x到不了m,则mx+=x
else if(mn+x <= m) mx=((mn+x)%2 == m%2)?m:m-1; //如果mn+x落在区间内,则可以达到m或者m-1,由mn+x和m的奇偶性决定结果是m或m-1
else mx=m+m-mn-x; //否则x中需要有m-mn个用来把0翻成1,剩余的x-(m-mn)个用来把1翻成0,剩余1个数为m-(x-(m-mn))
mn=p;
}
f[0]=1;
for(int i=1;i<=mx;i++)
{
if(m-i < i) f[i]=f[m-i];
else f[i]=f[i-1]*(m-i+1)%MOD*mod_exp(i,MOD-2,MOD)%MOD;
}
LL ans=0;
for(int i=mn;i<=mx;i+=2)
ans=(ans+f[i])%MOD;
pf64(ans);
}
return 0;
}


Lucas定理求解(时间上略快):

LL n,m,a;
LL fac[N];

void init(LL p)
{
LL i;
fac[0] =1;
for(i=1; i <= N-10; i++)
fac[i] = fac[i-1]*i % p;
}

LL exp_mod(LL a, LL b, LL p)
{
LL tmp = a % p, ans =1;
while(b)
{
if(b & 1) ans = ans * tmp % p;
tmp = tmp*tmp % p;
b >>=1;
}
return ans;
}

LL C(LL n, LL m, LL p)
{
if(m > n)
return 0;
return fac[n]*exp_mod(fac[m]*fac[n-m], p-2, p) % p;//逆元
}

LL Lucas(LL n, LL m, LL p)
{
if(m ==0)
return 1;
return (C(n%p, m%p, p)*Lucas(n/p, m/p, p))%p;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
init(MOD);
while(sf264(n,m)!=EOF)
{
LL p,mn=0,mx=0;
fr(n){
sf64(a);
//update mn
if(a <= mn) p=mn-a;
else if(a <= mx) p=(a%2 == mn%2)?0:1;
else p=a-mx;

//update mx
if(m-a >= mx) mx=mx+a;
else if(m-a >= mn) mx=((mn+a)%2 == m%2)?m:m-1;
else mx=m+m-mn-a;
mn=p;
}
LL ans=0;
for(LL i=mn;i<=mx;i+=2)
ans=(ans+Lucas(m,i,MOD))%MOD;
pf64(ans);
}
return 0;
}

  评论这张
 
阅读(1023)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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