[AH2017/HNOI2017]抛硬币（扩展lucas）

推式子+exlucas。

题意：

小 A 和小 B 是一对好朋友，两个人同时抛 b 次硬币，如果小 A 的正面朝上的次数大于小 B 正面朝上的次数，则小 A 获胜。

小 A 决定在小 B 没注意的时候作弊，悄悄地多抛几次硬币，当然，为了不让小 B 怀疑，他不会抛太多次。

现在小 A 想问你，在多少种可能的情况下，他能够胜过小 B 呢？由于答案可能太大，所以你只需要输出答案在十进制表示下的最后 k 位即可。

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

\(a,b\leq10^{15}\)，\(b\leq a\leq b+10000\)，\(k\leq9\)。

看起来不太好做，但注意到\(b\leq a\leq b+10000\)。即\(0\leq a-b \leq 10000\)。

考虑两种情况：

1、在小A投b次时，就胜过小B。

先考虑前b个：总数为\(2^{b+b}\)，前b个相等的有\(C(b,i)^2\)之和，即\(C(b+b,b)\)。

由于大于和小于等价，所以方案数为\(({2^{b+b}}-C(b+b,b))*2^{a-b}/2\)。

由于\(C(b+b,b)=C(b+b-1,b)+C(b+b-1,b-1)=2C(b+b-1,b)\)，所以原式=\(({2^{b+b}}-C(b+b-1,b))*2^{a-b}\)。

2、在小A投b次时，没有胜过小B。

设小A前b次有x次，后a-b次有z次，小B有y次。则\(x+z>y\)，即\(y-x<z\)。设\(i=y-x，z>i\)。

枚举i，则前b个方案数为\(C(b,x)*C(b,x+i)\)之和，即\(C(b,b-x)*C(b,x+i)\)之和，等于\(C(b+b,b+i)\)。

后a-b个方案数为\(C(a-b,z)(z>i)\)之和，可以枚举时维护后缀和。

但是，模数为\(10^k\)，不是质数，很讨厌，需要exlucas。

首先，计算出\(C(n,m)mod 2^k\)，\(C(n,m)mod 5^k\)，通过中国剩余定理，可以算出\(C(n,m)mod 10^k\)。

以\(5^k\)为例：

因为\(5^k\)不是质数，不能lucas，需要用\(C(n,m)=n!/(m!*(n-m)!)\)计算。

然而，由于m很大时，\(m! mod 5^k=0\)，无法求逆元。

所以，把\(n!,m!,(n-m)!\)中的5都拆出来，即化成\(a*5^b\)的性质。

暴力拆：例如\(k=2\)，\(n=60\)。

\(60!=1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29*30*31*32*33*34*35*36*37*38*39*40*41*42*43*44*45*46*47*48*49*50*51*52*53*54*55*56*57*58*59*60\)。

把5提出，

\(60!=1*2*3*4*6*7*8*9*11*12*13*14*16*17*18*19*21*22*23*24*26*27*28*29*31*32*33*34*36*37*38*39*41*42*43*44*46*47*48*49*51*52*53*54*56*57*58*59*12!*5^{12}\)。

12!可以递归，考虑前面一堆：

我们发现，在mod25意义下，

\(1*2*3*4*6*7*8*9*11*12*13*14*16*17*18*19*21*22*23*24=26*27*28*29*31*32*33*34*36*37*38*39*41*42*43*44*46*47*48*49\)。

就是mod25后，有一堆循环节，所以只要算出\(1*2*3*4*6*7*8*9*11*12*13*14*16*17*18*19*21*22*23*24\)，然后快速幂即可。

后面还有零散的\(51*52*53*54*56*57*58*59\)，暴力算即可。

但是，这个算法需要\(5^9*10000*10\)次计算，显然超时。

考虑预处理：

首先，\(1*2*3*4*6*7*8*9*11*12*13*14*16*17*18*19*21*22*23*24\)可以预处理出。

其次，零散的\(51*52*53*54*56*57*58*59\)是一个前缀积，也可以预处理出。

这样，一次exlucas就是\(O(log^2n)\)的了（有快速幂的log）。

然而还是超时，考虑剪枝：

对于\(n!=a*x^b\)，其中b可以很快算出。所以\(C(n,m)=a*x^b\)，求出b如果大于等于k，则为0。

这样就很快了。

代码：

#include <stdio.h>

#define ll long long

int md;

int ksm(int a, ll b) {

	int jg = 1;

	while (b > 0) {

		if (b & 1) jg = 1ll * jg * a % md;

		a = 1ll * a * a % md;

		b = (b >> 1);

	}

	return jg;

}

int j2[520],j5[1953130],m2,m5,m21,m51;

void dfs2(ll n, int & a, ll & b, int xk) {

	if (n == 0) return;

	int ta = 1;

	ll tb = 0;

	dfs2(n >> 1, ta, tb, xk);

	a = 1ll * a * ta % md;

	b += tb + (n >> 1);

	if (n >= xk) a = 1ll * a * ksm(j2[xk - 1], n / xk) % md;

	a = 1ll * a * j2[n - (n / xk) * xk] % md;

}

void dfs5(ll n, int & a, ll & b, int xk) {

	if (n == 0) return;

	int ta = 1;

	ll tb = 0;

	dfs5(n / 5, ta, tb, xk);

	a = 1ll * a * ta % md;

	b += tb + n / 5;

	if (n >= xk) a = 1ll * a * ksm(j5[xk - 1], n / xk) % md;

	a = 1ll * a * j5[n - (n / xk) * xk] % md;

}

ll jisuan(ll tn, int x) {

	ll ms = 0;

	while (tn > 0) {

		ms += tn / x;

		tn /= x;

	}

	return ms;

}

int getC2(ll n, ll m, int k) {

	if (jisuan(n, 2) - jisuan(m, 2) - jisuan(n - m, 2) >= k) return 0;

	int a1 = 1,	a2 = 1,	a3 = 1;

	ll b1 = 0,	b2 = 0,	b3 = 0;

	dfs2(n, a1, b1, m2);

	dfs2(m, a2, b2, m2);

	dfs2(n - m, a3, b3, m2);

	b1 -= (b2 + b3);

	a1 = 1ll * a1 * ksm(1ll * a2 * a3 % md, m21 - 1) % md;

	return 1ll * a1 * ksm(2, b1) % m2;

}

int getC5(ll n, ll m, int k) {

	if (jisuan(n, 5) - jisuan(m, 5) - jisuan(n - m, 5) >= k) return 0;

	int a1 = 1,	a2 = 1,	a3 = 1;

	ll b1 = 0,	b2 = 0,	b3 = 0;

	dfs5(n, a1, b1, m5);

	dfs5(m, a2, b2, m5);

	dfs5(n - m, a3, b3, m5);

	b1 -= (b2 + b3);

	a1 = 1ll * a1 * ksm(1ll * a2 * a3 % md, m51 - 1) % md;

	return 1ll * a1 * ksm(5, b1) % m5;

}

int c2,c5;

int C(ll n, ll m, int k) {

	if (m < 0 || m > n) return 0;

	int z2 = getC2(n, m, k);

	int z5 = getC5(n, m, k);

	return (1ll * z2 * c2 + 1ll * z5 * c5) % md;

}

int main() {

	ll a,b;

	int k,

	lk = -1;

	while (scanf("%lld%lld%d", &a, &b, &k) == 3) {

		if (k != lk) {

			md = 1;

			for (int i = 0; i < k; i++) md *= 10;

			m2 = ksm(2, k);

			m5 = ksm(5, k);

			m21 = ksm(2, k - 1);

			m51 = 4 * ksm(5, k - 1);

			c2 = 1ll * m5 * ksm(m5 % m2, m21 - 1) % md;

			c5 = 1ll * m2 * ksm(m2, m51 - 1) % md;

			j2[0] = j5[0] = 1;

			for (int i = 1; i < m2; i++) {

				j2[i] = j2[i - 1];

				if (i % 2 != 0) j2[i] = 1ll * j2[i] * i % md;

			}

			for (int i = 1; i < m5; i++) {

				j5[i] = j5[i - 1];

				if (i % 5 != 0) j5[i] = 1ll * j5[i] * i % md;

			}

		}

		int ans = 1ll * (ksm(2, b + b - 1) - C(b + b - 1, b, k) + md) % md * ksm(2, a - b) % md;

		for (int i = a - b - 1, h = 0; i >= 0; i--) {

			h = (h + C(a - b, i + 1, k)) % md;

			ans = (ans + 1ll * C(b + b, b + i, k) * h) % md;

		}

		char zf[20];

		sprintf(zf, "%d", ans + md);

		printf("%s\n", zf + 1);

		lk = k;

	}

	return 0;

}

巴特西

[AH2017/HNOI2017]抛硬币（扩展lucas）

最新文章

热门文章