【刷题】BZOJ 4830 [Hnoi2017]抛硬币

Description

小A和小B是一对好朋友,他们经常一起愉快的玩耍。最近小B沉迷于**师手游,天天刷本,根本无心搞学习。但是已经入坑了几个月,却一次都没有抽到SSR,让他非常怀疑人生。勤勉的小A为了劝说小B早日脱坑,认真学习,决定以抛硬币的形式让小B明白他是一个彻彻底底的非洲人,从而对这个游戏绝望。两个人同时抛b次硬币,如果小A的正面朝上的次数大于小B正面朝上的次数,则小A获胜。但事实上,小A也曾经沉迷过拉拉游戏,而且他一次UR也没有抽到过,所以他对于自己的运气也没有太大把握。所以他决定在小B没注意的时候作弊,悄悄地多抛几次硬币,当然,为了不让小B怀疑,他不会抛太多次。现在小A想问你,在多少种可能的情况下,他能够胜过小B呢?由于答案可能太大,所以你只需要输出答案在十进制表示下的最后k位即可。

Input

有多组数据,对于每组数据输入三个数a,b,k,分别代表小A抛硬币的次数,小B抛硬币的次数,以及最终答案保留多少位整数。

1≤a,b≤10^15,b≤a≤b+10000,1≤k≤9,数据组数小于等于10。

Output

对于每组数据,输出一个数,表示最终答案的最后k位为多少,若不足k位以0补全。

Sample Input

2 1 9

Sample Output

000000004
6
3 2 1

【样例解释】

对于第一组数据,当小A抛2次硬币,小B抛1次硬币时,共有4种方案使得小A正面朝上的次数比小B多。(01,0),(10,0),(11,0),(11,1)

对于第二组数据,当小A抛3次硬币,小B抛2次硬币时,共有16种方案使得小A正面朝上的次数比小B多。(001,00),(010,00),(100,00),(011,00),(101,00),(110,00),(111,00),(011,01),(101,01),(110,01),(111,01),(011,10),(101,10),(110,10),(111,10),(111,11)

Solution

膜拜litble大佬

大佬思路很巧妙啊

首先把两个人抛硬币的结果接在一起作为一个01序列;那么对于小A胜利的情况就是前 \(a\) 项包含的1大于后 \(b\) 项包含的1,对于小B胜利的情况正好相反,但是如果把小B胜利的序列所有位置都异或1,那么新序列对应的一定是一个小A胜利的序列;所以小A和小B胜利的序列是可以相互转化的,且一一对应,所以正常情况下,小A胜利和小B胜利各占一半,即 \(\frac{2^{a+b}}{2}\)

  • 当 \(a=b\) 的时候,要减去平局的情况,答案是 \(\frac{2^{a+b}-C_{a+b}^a}{2}\) 。为什么平局的情况是 \(C_{a+b}^a\) ?这个得换一种构建序列的思路,小A抛硬币是正面为1,反面为0,而小B抛硬币是正面为0,反面为1,;这样构建,如果他们抛出硬币是正面的次数相等,那么序列里1的数量一定等于0的数量,又 \(a=b\) ,所以就是 \(a+b\) 里选 \(a\) 个当1,即 \(C_{a+b}^a\)

  • 当 \(a>b\) 的时候,会出现这样一种情况:01序列异或1之后前 \(a\) 项包含1的个数仍然大于后 \(b\) 项包含1的个数。这样的情况我们要额外加上。对于这样的情况,设原序列中小B \(i\) 次正面,而小A比小B多 \(j\) 次正面,因为异或1之后的序列仍然小A的1更多,即 \(b-i<a-i-j\) ,所以 \(j<a-b\)

那么 \(extra=\frac{\sum_{i=0}^b\sum_{j=1}^{a-b-1}C_b^iC_a^{i+j}}{2}=\frac{\sum_{i=0}^b\sum_{j=1}^{a-b-1}C_b^{b-i}C_a^{i+j}}{2}\)

然后怎么办?

litble大佬给出了一种理解方法

那么我们可以这么看这个式子:我们在 \(a+b\) 个数组成的序列中选择 \(b+j\) 个元素变成1,然后其中在前 \(b\) 个元素中的1的个数就正好能完成那个和 \(i\) 有关的枚举。

所以额外的贡献又变成了:\(extra=\frac{\sum_{i=1}^{a-b-1}C_{a+b}^{b+i}}{2}\)

好好变式子:\(extra=\frac{\sum_{i=b+1}^{a-1}C_{a+b}^i}{2}=\sum_{i=\lceil \frac{a+b}{2} \rceil}^{a-1}C_{a+b}^i+[2|a+b]\frac{C_{a+b}^{\frac{a+b}{2}}}{2}\)

所以 \(ans=2^{a+b-1}+extra\)

就差不多了,然后暴力枚举,用拓展Lucas求组合数

几个问题:

  • 怎么用扩展Lucas?

发现模数是10的多少次方,这一定可以变成一个2的多少次方乘5的多少次方;这两个东西正好满足扩展Lucas的形式,所以可以求

  • 要预处理吗?

要。因为模数只会是10的多少次方,那就把2和5在扩展Lucas求fac之中的for循环枚举的乘积先预处理存下来,大大节省时间,不加这个不行

  • 为什么 \(extra\) 一定要化到最后一步呢?

两个原因。一是可以节省时间;二是保证正确性。我们在求Lucas中对于除2的处理很特殊,在模数是5的多少次方时,因为2和5的多少次方互质,所以可以直接扩欧求逆元乘上去,但如果是2的多少次方当模数的时候,2是没有逆元的,怎么办?那就只能在扩展Lucas里提因子 \(pi=2\) 时,把最后要乘的2的次方减去一个1。但是这样肯定会有问题,因为组合数是有奇数的,这时没有2因子,毫无办法,没救了。而最后一步式子利用杨辉三角的对称性把左右两边的一起算,算2倍的,除2之后就是本身的值,唯一多出来的就是后面的 \([2|a+b]\frac{C_{a+b}^{\frac{a+b}{2}}}{2}\) ,但这个式子要不前面条件不成立,要么一定有2因子(画一画杨辉三角),所以可以保证答案正确性

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=100+10,MAX2=512,MAX5=1953125;
ll a,b,k,Mod,p1,p2,pk1,pk2,f[2][MAX5+10];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline ll qexp(ll a,ll b,ll n)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%n;
a=a*a%n;
b>>=1;
}
return res;
}
inline ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll r=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-(a/b)*y;
return r;
}
inline ll fac(ll n,ll pi,ll pk)
{
if(!n)return 1;
else return qexp(f[pi!=2][pk],n/pk,pk)*f[pi!=2][n%pk]%pk*fac(n/pi,pi,pk)%pk;
}
inline ll inv(ll n,ll p)
{
ll x,y;
exgcd(n,p,x,y);
return (x+p)%p==0?p:(x+p)%p;
}
inline ll C(ll n,ll m,ll pi,ll pk,bool nd)
{
if(n<m)return 0;
ll ki=0;
for(register ll i=n;i;i/=pi)ki+=i/pi;
for(register ll i=m;i;i/=pi)ki-=i/pi;
for(register ll i=n-m;i;i/=pi)ki-=i/pi;
if(pi==2&&nd)ki--;
if(ki>=k)return 0;
ll Mul1=fac(n,pi,pk),Mul2=fac(m,pi,pk),Mul3=fac(n-m,pi,pk),inv2=inv(2,pk);
return Mul1*inv(Mul2,pk)%pk*inv(Mul3,pk)%pk*qexp(pi,ki,pk)%pk*(pi==5&&nd?inv2:1)%pk;
}
inline ll CRT(ll B,ll W)
{
return B*(Mod/W)%Mod*inv(Mod/W,W)%Mod;
}
inline ll exLucas(ll n,ll m,bool nd)
{
p1=2,p2=5;
pk1=1,pk2=1;
for(register int i=1;i<=k;++i)pk1*=p1,pk2*=p2;
return (CRT(C(n,m,p1,pk1,nd),pk1)+CRT(C(n,m,p2,pk2,nd),pk2))%Mod;
}
inline void init()
{
f[0][0]=f[1][0]=1;
for(register int i=1;i<=MAX2;++i)
if(i%2)f[0][i]=1ll*f[0][i-1]*i%MAX2;
else f[0][i]=f[0][i-1];
for(register int i=1;i<=MAX5;++i)
if(i%5)f[1][i]=1ll*f[1][i-1]*i%MAX5;
else f[1][i]=f[1][i-1];
}
int main()
{
init();
while(scanf("%lld%lld%d",&a,&b,&k)!=EOF)
{
Mod=1;
for(register int i=1;i<=k;++i)Mod*=10;
ll res=0;
if(a==b)res=(qexp(2,a+b-1,Mod)-exLucas(a+b,a,1)+Mod)%Mod;
else
{
res=qexp(2,a+b-1,Mod);
for(register ll i=(a+b)/2+1;i<a;++i)(res+=exLucas(a+b,i,0))%=Mod;
if((a+b)%2==0)(res+=exLucas(a+b,(a+b)/2,1))%=Mod;
}
while(res<(Mod/10))write(0),Mod/=10;
write(res,'\n');
}
return 0;
}
上一篇:[Go] 跨平台文件系统监控工具 fsnotify 应用举例


下一篇:[AH/HNOI2017]抛硬币