[AH2017HNOI2017]抛硬币

一、题目

点此看题

二、解法

前置芝士：范德蒙德卷积： $$C(n+m,k)=\sum _{i=0}^{k}C(n,i)C(m,k-i)$$这道题的暴力算式是很好写的，但是优化不动，因为用不到$a-b\le 10000$，从最简单的情况考虑：

部分分：a=b

此时$a,b$公平竞争，对于$a$赢着的情况，一定严格对应一种$a$输着的情况（把他们的输赢情况反转），那么我们考虑算出他们平局的情况，用所有情况减去除$2$即是答案，平局算式如下： $$\sum _{i=0}^{a}C(a,i{)}^2=\sum _{i=0}^{a}C(a,i)C(a,a-i)=C(2a,a)$$所以答案是： $$\frac{2^{a+b}-C(2a,a)}{2}$$a>b

有点难，按照部分分的对应法则我们发现有些$a$赢的情况反转时候还是赢的，我们称这种现象叫不对称，记对称的方案数是$S_1$，不对称的方案数是$S_2$，则有这样的关系： $$S_1+S_2=2^{a+b},ans=\frac{S_1}{2}+S_2$$我们只需要求出其中一个就行了，求对称的只能暴力，所以我们去算$S_2$，我们考虑此时满足什么样的关系，用形式上的表达，记$|a|$是$a$的$1$个数，$|b|$是$b$的$1$个数： $$|a|>|b|,a-|a|>b-|b|$$也就是$a-b>|a|-|b|$，这时候出现了$a-b$就很舒服了，盯准它，枚举$|b|$和$|a|-|b|$： $$S_2=\sum _{i=0}^{b}C(b,i)\sum _{j=1}^{a-b-1}C(a,i+j)$$$$\sum _{j=1}^{a-b-1}\sum _{i=0}^{b}C(b,b-i)C(a,i+j)$$$$\sum _{j=1}^{a-b-1}C(a+b,b+j)$$然后用算出上式这道题就结束了，模数其实是$1e9$，非质数，考虑扩展卢卡斯，$10^9=2^9{5}^9$，对两个质数次幂做卢卡斯然后$\mathtt{c}\mathtt{r}\mathtt{t}$合并就行了，需要预处理对于质因子$2$和$5$的阶乘，算卢卡斯就可以$O({\log }^2)$了（需要快速幂）

还有问题，最后的除$2$怎么解决，$2$的次幂可以直接搞指数，对于我们算的组合数由于是杨辉三角上的$1$行，具有其对称性，只用算一边就可以了，而如果$a+b$是偶数$C(a+b,(a+b)/2)$没有配对的，把他化到上一行变成$C(a+b-1,(a+b)/2)$就行了。还有一种方法就是把模数变成$2e9$最后就可以直接除$2$了。

#include <cstdio> const int p = 1e9; #define int long long int read() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int n,m,a,b,k,y[20],mod[2]={512,1953125},bs[2]={2,5},fac[2][2000000]; void exgcd(int a,int b,int &x,int &y) { if(!b){x=1;y=0;return ;} exgcd(b,a%b,y,x);y-=x*(a/b); } int inv(int v,int p) { int x,y;exgcd(v,p,x,y); return (x%p+p)%p; } int qkpow(int a,int b,int p) { int r=1; while(b>0) { if(b&1) r=r*a%p; a=a*a%p; b>>=1; } return r; } int fuck(int n,int t) { if(!n) return 1; return qkpow(fac[t][mod[t]-1],n/mod[t],mod[t]) *fac[t][n%mod[t]]%mod[t]*fuck(n/bs[t],t)%mod[t]; } int L(int n,int m,int t) { int ind=0; for(int i=n;i;i/=bs[t]) ind+=i/bs[t]; for(int i=m;i;i/=bs[t]) ind-=i/bs[t]; for(int i=n-m;i;i/=bs[t]) ind-=i/bs[t]; if(ind>=9) return 0; int x=fuck(n,t),y=fuck(m,t),z=fuck(n-m,t); return x*inv(y,mod[t])%mod[t]*inv(z,mod[t])%mod[t]*qkpow(bs[t],ind,mod[t])%mod[t]; } void pr(int x) { for(int i=1;i<=k;i++,x/=10) y[i]=x%10; for(int i=k;i>=1;i--) printf("%lld",y[i]); puts(""); } signed main() { fac[0][0]=fac[1][0]=1; for(int i=1;i<mod[0];i++) fac[0][i]=(i%2)?i*fac[0][i-1]%mod[0]:fac[0][i-1]; for(int i=1;i<mod[1];i++) fac[1][i]=(i%5)?i*fac[1][i-1]%mod[1]:fac[1][i-1]; while(~scanf("%lld %lld %lld",&a,&b,&k)) { int r2=0,r5=0; if(a==b)//求C(2a,a) { r2=L(2*a-1,a,0);r5=L(2*a-1,a,1); r2=r2*mod[1]%p*inv(mod[1],mod[0])%p; r2=(r2+r5*mod[0]%p*inv(mod[0],mod[1])%p)%p; pr((qkpow(2,a+b-1,p)-r2+p)%p); } else { if((a+b)%2)//对称，算一边 { for(int i=b+1;i<=(a+b)/2;i++) r2=(r2+L(a+b,i,0))%p; for(int i=b+1;i<=(a+b)/2;i++) r5=(r5+L(a+b,i,1))%p; r2=r2*mod[1]%p*inv(mod[1],mod[0])%p; r2=(r2+r5*mod[0]%p*inv(mod[0],mod[1])%p)%p; pr((qkpow(2,a+b-1,p)+r2)%p); } else//单独算C(a+b,(a+b)/2) { for(int i=b+1;i<(a+b)/2;i++) r2=(r2+L(a+b,i,0))%p;r2=(r2+L(a+b-1,(a+b)/2,0))%p; for(int i=b+1;i<(a+b)/2;i++) r5=(r5+L(a+b,i,1))%p;r5=(r5+L(a+b-1,(a+b)/2,1))%p; r2=r2*mod[1]%p*inv(mod[1],mod[0])%p; r2=(r2+r5*mod[0]%p*inv(mod[0],mod[1])%p)%p; pr((qkpow(2,a+b-1,p)+r2)%p); } } } }