[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\leqslant a,b\leqslant 10^{15},b\leqslant a\leqslant b+10^4,1\leqslant k\leqslant 9\)，数据组数小于等于10。

Output

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

Sample Input

2 1 9

Sample Output

000000004

6

3 2 1

题目要求

\[\sum\limits_{i=0}^b\binom{b}{i}\sum\limits_{j=i+1}^a\binom{a}{j}
\]

暴力可以过30pts，后缀和优化一下，可以拿到70pts(考场上拿了70分就赶快想其他题去)

怎么拿到满分嘞？我们来推柿子

\[\begin{align}Ans&=\sum\limits_{i=0}^b\binom{b}{i}\sum\limits_{j=i+1}^a\binom{a}{j}\nonumber\\&=\sum\limits_{i=0}^b\binom{b}{i}(2^a-\sum\limits_{j=0}^i\binom{a}{j})\nonumber\\&=2^{a+b}-\sum\limits_{i=0}^b\sum\limits_{j=0}^i\binom{b}{i}\binom{a}{j}\nonumber\end{align}
\]

我们令\(i+j=k\)，那么后面那部分的式子变为

\[\begin{align}\sum\limits_{i=0}^b\sum\limits_{j=0}^i\binom{b}{i}\binom{a}{j}&=\sum\limits_{i=0}^b\sum\limits_{k=i}^{2i}\binom{b}{i}\binom{a}{k-i}\nonumber\\&=\sum\limits_{k=0}^{b}\sum\limits_{i=0}^k\binom{b}{i}\binom{a}{k-i}\nonumber\end{align}
\]

\(\sum\limits_{i=0}^k\binom{b}{i}\binom{a}{k-i}\)相当于枚举\(k\)中的部分在\(a\)中或在\(b\)中，所以\(\sum\limits_{i=0}^k\binom{b}{i}\binom{a}{k-i}=\binom{a+b}{k}\)

所以原式可以变成

\[Ans=2^{a+b}-\sum\limits_{k=0}^{b}\binom{a+b}{k}
\]

然后就可以暴力枚举了……还是70pts啊喂，难道优化没啥用？

肯定有用的！我们考虑一下数据中还有一个条件没有用上：\(b-a\leqslant 10^4\)

我们将杨辉三角第\(a+b\)行的前\(b\)个元素标记一下，由于对称，所以我们把后\(b\)个元素也标记一下，可以发现，没有标记的元素至多只有\(2(a-b)\)个！

我们可以\(O(a-b)\)减去中间那部分，然后除2即可，所以答案为

\[\begin{align}Ans&=2^{a+b}-\dfrac{2^{a+b}-\sum\limits_{i=b+1}^{a+1}\binom{a+b}{i}}{2}\nonumber\\&=2^{a+b-1}+\dfrac{\sum\limits_{i=b+1}^{a+1}\binom{a+b}{i}}{2}\nonumber\end{align}
\]

做完了吗？并没有，2在\(10^x\)下没有逆元……所以这个方法不可行

考虑一下\(\sum\limits_{i=b+1}^{a+1}\binom{a+b}{i}\)这部分也是有对称的！除了\(a+b\)为偶数时……会单出来一个\(\binom{a+b}{(a+b)/2}\)

但其实，\(\binom{a+b}{(a+b)/2)}=\binom{a+b-1}{(a+b)/2-1}+\binom{a+b-1}{(a+b)/2}\)，我们可以发现，\(\binom{a+b-1}{(a+b)/2-1}=\binom{a+b-1}{(a+b)/2}\)

所以\(\dfrac{\binom{a+b}{(a+b)/2}}{2}=\binom{a+b-1}{(a+b)/2-1}=\binom{a+b-1}{(a+b)/2}\)

那么最终答案为

\[Ans=2^{a+b-1}+\sum\limits_{i=b+1}^{\lfloor(a+b-1)/2\rfloor}\binom{a+b}{i}+\binom{a+b-1}{(a+b)/2}[(a+b)\%2=0]
\]

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define it iterator

#define vt value_type

#define inf 0x7f7f7f7f

typedef long long ll;

typedef long double ld;

typedef unsigned int ui;

typedef unsigned long long ull;

inline char gc(){

	static char buf[1000000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

template<typename T>inline T frd(T x){

	int f=1; char ch=gc();

	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

template<typename T>inline T read(T x){

	int f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x<0)    putchar('-'),x=-x;

	if (x>9)	print(x/10);

	putchar(x%10+'0');

}

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;}

template<typename T>inline T swap(T &x,T &y){T t=x; x=y,y=t;}

const int N=2e6;

namespace Math{

	int P[3],V[3],C[3],f[3][N+10],SP;

	int mlt(int a,ll b,int p=inf){

		int res=1;

		for (;b;b>>=1,a=1ll*a*a%p)	if (b&1)	res=1ll*res*a%p;

		return res;

	}

	void prepare(int p){

		P[1]=2,V[1]=f[1][0]=1,C[1]=0;

		while (p%2==0)	V[1]<<=1,p>>=1,C[1]++;

		for (int i=1;i<=V[1];i++)	f[1][i]=1ll*f[1][i-1]*(i%2?i:1)%V[1];

		P[2]=5,V[2]=f[2][0]=1,C[2]=0;

		while (p%5==0)	V[2]*=5,p/=5,C[2]++;

		for (int i=1;i<=V[2];i++)	f[2][i]=1ll*f[2][i-1]*(i%5?i:1)%V[2];

		SP=V[1]*V[2];

	}

	int gcd(int a,int b){return !b?a:gcd(b,a%b);}

	void exgcd(int a,int b,int &x,int &y){

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

		exgcd(b,a%b,x,y);

		int t=x; x=y,y=t-a/b*y;

	}

	int Ex_GCD(int a,int b,int c){

		int d=gcd(a,b),x,y;

		if (c%d)	return -1;

		a/=d,b/=d,c/=d;

		exgcd(a,b,x,y);

		x=(1ll*x*c%b+b)%b;

		return x;

	}

	int work(ll n,int i){

		if (n<=1)	return 1;

		int res=1ll*mlt(f[i][V[i]],n/V[i],V[i])*f[i][n%V[i]]%V[i];

		return 1ll*res*work(n/P[i],i)%V[i];

	}

	ll count(ll n,int i){return n<P[i]?0:count(n/P[i],i)+n/P[i];}

	int calc(ll n,ll m,int i){

		ll cnt=count(n,i)-count(m,i)-count(n-m,i);

		if (C[i]<=cnt)	return 0;

		return 1ll*work(n,i)*Ex_GCD(work(m,i),V[i],1)%V[i]*Ex_GCD(work(n-m,i),V[i],1)%V[i]*mlt(P[i],cnt)%V[i];

	}

	int Ex_C(ll n,ll m){

		if (n<m)	return 0;

		int Ans=0;

		Ans=(Ans+1ll*Ex_GCD(SP/V[1],V[1],1)*(SP/V[1])%SP*calc(n,m,1)%SP)%SP;

		Ans=(Ans+1ll*Ex_GCD(SP/V[2],V[2],1)*(SP/V[2])%SP*calc(n,m,2)%SP)%SP;

		return Ans;

	}

}

using namespace Math;

int main(){

	ll a,b; int p,last=0;

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

		p=mlt(10,p); int Ans=0;

		if (p!=last)	prepare(last=p);

		if (a==b){

			Ans=mlt(2,a+b-1,p)-Ex_C(a+b-1,a-1);

			Ans=(Ans%p+p)%p;

			while (Ans<p/10)	putchar('0'),p/=10;

			printf("%d\n",Ans);

			continue;

		}

		if ((a+b)%2==0)	Ans=Ex_C(a+b-1,((a+b)>>1)-1);

		for (ll i=b+1;i<(a+b+1)>>1;i++)	Ans=(Ex_C(a+b,i)+Ans)%p;

		Ans=mlt(2,a+b-1,p)+Ans;

		Ans=(Ans%p+p)%p;

		while (Ans<p/10)	putchar('0'),p/=10;

		printf("%d\n",Ans);

	}

	return 0;

}

巴特西

[HNOI2017]抛硬币

最新文章

热门文章