传送门

数学真的太优秀了Orz

数据真的太优秀了Orz

题目描述

小 A 和小 B 是一对好朋友，他们经常一起愉快的玩耍。最近小 B 沉迷于**师手游，天天刷本，根本无心搞学习。但是已经入坑了几个月，却一次都没有抽到 SSR，让他非常怀疑人生。勤勉的小 A 为了劝说小 B 早日脱坑，认真学习，决定以抛硬币的形式让小 B 明白他是一个彻彻底底的非洲人，从而对这个游戏绝望。两个人同时抛 b 次硬币，如果小 A 的正面朝上的次数大于小 B 正面朝上的次数，则小 A 获胜。

但事实上，小 A 也曾经沉迷过拉拉游戏，而且他一次 UR 也没有抽到过，所以他对于自己的运气也没有太大把握。所以他决定在小 B 没注意的时候作弊，悄悄地多抛几次硬币，当然，为了不让小 B 怀疑，他不会抛太多次。现在小 A 想问你，在多少种可能的情况下，他能够胜过小 B 呢？由于答案可能太大，所以你只需要输出答案在十进制表示下的最后 k 位即可。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

2 1 9

3 2 1

输出样例#1：

000000004

6

说明

对于第一组数据，当小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).

数据范围

题解

留坑qwq

code:

//By Menteur_Hxy

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#define R register

using namespace std;

typedef long long LL;

LL a,b,k,md,ans,K2,K5;

LL fac2[1050],fac5[2000000];

inline LL qpow(LL a,LL b,LL p) {

	R LL ret=1;

	while(b) {

		if(b&1) ret=ret*a%p;

		a=a*a%p; b>>=1;

	}

	return ret;

}

void init() {

	int M2=512,M5=1953125;

	fac2[0]=fac5[0]=1;

	for(R int i=1;i<=M2;i++)

		fac2[i]=fac2[i-1]*((i&1)?i:1)%M2;

	for(R int i=1;i<=M5;i++)

		fac5[i]=fac5[i-1]*(i%5?i:1)%M5;

}

inline void exgcd(LL a,LL b,LL &x,LL &y) {

	if(!b) {x=1,y=0;return ;}

	exgcd(b,a%b,x,y); LL tmp=x;

	x=y; y=tmp-(a/b)*y;

}

inline LL inv(LL a,LL p) {

	LL x,y;

	exgcd(a,p,x,y);

	return (x>p?x%p:x);

}

inline LL mul(LL x,int p,LL pk) {

	if(!x) return 1; R LL res=0;

	if(p&1) {res=qpow(fac5[pk],x/pk,pk)*fac5[x%pk]%pk;}

	else {res=qpow(fac2[pk],x/pk,pk)*fac2[x%pk]%pk;}

	return res*mul(x/p,p,pk)%pk;

}

inline LL C(LL a,LL b,int p,LL pk,bool fl) {

	if(a<b) return 0; LL tmp=0;

	for(R LL i=a;i;i/=p) tmp+=i/p;

	for(R LL i=b;i;i/=p) tmp-=i/p;

	for(R LL i=a-b;i;i/=p) tmp-=i/p;

	if(fl&&p==2) --tmp; if(tmp>=k) return 0;

	LL s1=mul(a,p,pk),s2=mul(b,p,pk),s3=mul(a-b,p,pk);

	R LL res=qpow(p,tmp,pk)*s1%pk*inv(s2,pk)%pk*inv(s3,pk)%pk;

	if(fl&&p==5) res=res*inv(2,pk)%pk;

	return res*(md/pk)%md*inv(md/pk,pk)%md;

}

inline LL lucas(LL a,LL b,bool fl) {return (C(a,b,2,K2,fl)+C(a,b,5,K5,fl))%md;}

const LL INF=1e9+5;

int main() {

	init();

	while(~scanf("%lld%lld%lld",&a,&b,&k)) {

		md=qpow(10,k,INF); ans=qpow(2,a+b-1,md);

		K2=qpow(2,k,INF); K5=qpow(5,k,INF);

		if(a==b) ans=(ans-lucas(a<<1,a,1)+md)%md;

		else {

			for(R LL i=(a+b)/2+1;i<a;i++) ans=(ans+lucas(a+b,i,0))%md;

			if((a+b)%2==0) ans=(ans+lucas(a+b,(a+b)/2,1))%md;

		}

		while(ans<md/10) putchar('0'),md/=10;

		printf("%lld\n",ans);

	}

	return 0;

}