LGP3726题解

确实牛逼。。。。。。这个转化我反正肯定想不到。。。

考虑 \(a=b\) 的情况。发现出了平局之外都是一半赢一半输。可以得到此时的答案为：

\[\frac{2^{a+b}-\sum_{i=0}^{a}\binom{a}{i}^2}{2}
\]

后面是范德蒙德卷积，可以得到答案是 \(\frac{2^{a+b}-\binom{2a}{a}}{2}\)。

接下来考虑 \(a\neq b\)。前面的情况相当于是考虑将一个赢的方案和输的方案配对，所以我们考虑这个问题的时候也考虑将赢的方案和输的方案配对。

设能够配对的方案数为 \(q\)，不能够配对的方案数为 \(p\)，容易发现不能够配对的方案数一定是小 A 能够胜利的方案数。

答案就是 \(p+\frac{q}{2}\)。

只要能够计算出其中一个就可以了。考虑计算不能配对的方案数。

设 \(x\) 为小 A 的方案中硬币朝上的次数，\(y\) 为小 B 的方案中硬币朝上的次数。

如果一个方案不能配对必定满足 \(x>y\) 和 \(a-x>b-y\)，即 \(a-b>x-y\)。于是我们可以枚举这个 \(x-y\)：

\[\sum_{i=0}^{b}\sum_{j=1}^{a-b-1}\binom{b}{i}\binom{a}{i+j}
\]

\[\sum_{j=1}^{a-b-1}\sum_{i=0}^{b}\binom{b}{b-i}\binom{a}{i+j}
\]

\[\sum_{j=1}^{a-b-1}\binom{a+b}{b+j}
\]

\[\sum_{i=1}^{a-b-1}\binom{a+b}{b+i}
\]

使用 exLucas 计算即可。

需要注意的是最后要除以一个 \(2\)，把模数乘上二，最后直接除以一个 \(2\) 即可。

#include<functional>

#include<cstdio>

using std::function;

typedef unsigned ui;

typedef __uint128_t LL;

typedef unsigned long long ull;

const ui pw2[11]={1,2,4,8,16,32,64,128,256,512,1024};

const ui pw5[11]={1,5,25,125,625,3125,15625,78125,390625,1953125,9765625};

const ui pw10[11]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

struct Barrett{

	ull m,b;

	Barrett(const ui&m=1):m(m),b(((LL(1)<<64)+m-1)/m){}

	friend inline ull operator%(const ull&a,const Barrett&mod){

		return a-mod.m*(LL(mod.b)*a>>64);

	}

};

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

	if(!b)return x=1,y=0,void();exgcd(b,a%b,y,x);y-=ui(a/b)*x;

}

inline ui inv(const ui&n,const ui&mod){

	int x,y;exgcd(n,mod,x,y);return x<0?x+mod:x>=mod?x-mod:x;

}

inline ui pow(ui a,ull b,const Barrett&mod){

	ui ans(1);for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;return ans;

}

inline ui pow(ui a,ull b,const ui mod){

	ui ans(1);for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;return ans;

}

struct exLucas{

	Barrett p,mod;

	ui P,MOD,fac[1953126];

	inline void init(const ui&tp,const ui&tmod){

		fac[0]=1;p=Barrett(P=tp);mod=Barrett(MOD=tmod);

		for(ui i=1,j=1;i<=MOD;++i,++j,j*=j!=P)fac[i]=1ull*fac[i-1]*(j?i:1)%mod;

	}

	inline ull g(const ull&n){

		ull pk(P),ans(0);while(pk<=n)ans+=n/pk,pk*=P;return ans;

	}

	inline ui f(const ull&n){

		return n?1ull*f(n/P)*pow(fac[MOD],n/MOD,mod)%mod*fac[n%mod]%mod:1;

	}

	inline ui operator()(const ull&n,const ull&m){

		ui c=pow(P,g(n)-g(m)-g(n-m),mod);

		return c?1ull*f(n)*inv(f(m),MOD)%mod*inv(f(n-m),MOD)%mod*c%mod:0;

	}

}C2,C5;

inline ui Solve(const ull&a,const ull&b,const ui&k){

	const ui&mod2=pw2[k+1],&mod5=pw5[k],&mod=mod2*mod5;

	ui ans(0);C2.init(2,mod2);C5.init(5,mod5);

	function<ui(const ull&,const ull&)>

	C=[&](const ull&n,const ull&m){

		return 1ull*(1ull*C2(n,m)*inv(mod5,mod2)%mod*mod5+1ull*C5(n,m)*inv(mod2,mod5)%mod*mod2)%mod;

	};

	if(a==b)return(pow(2,a+b,mod)+mod-C(a+b,a))/2%pow(10,k,2e9);

	for(ui i=1;i<a-b;++i)ans=(ans+C(a+b,b+i))%mod;

	return(pow(2,a+b,mod)+ans)/2%pow(10,k,2e9);

}

inline void write(const ui&n,const ui&k){

	for(ui i=k-1;i<k;--i)printf("%u",n/pw10[i]%10);printf("\n");

}

signed main(){

	ull a,b;ui k;

	while(~scanf("%llu%llu%u",&a,&b,&k))write(Solve(a,b,k),k);

}

巴特西

LGP3726题解

最新文章

热门文章