[bzoj 4830] [Hnoi2017]抛硬币

有多少个 (a位0-1串, b位0-1串), 满足前者的1多于后者? 输出十进制下最后k位. (1≤a,b≤10^15, b≤a≤b+10^4, 1≤k≤9, 每个测试点数据组数不多于10, 时限1.5s) 待求的式子即:

记得70%的数据满足a≤10^6. 只要能在单次的时间内求出就能拿到这部分的分数. 暴力消因子就可以了 TAT 本省只有Sengxian神犇拿到这些分. 存在被卡常的神犇. 存在我这种码了几小时却没搞清算法的复杂度的逗b......10组数据1.5s? 我一组数据就要跑2s......暴力递推那部分, 做减法忘记加上模数......最后只有a≤10的10分......

言归正传. 首先, 式子长成这样不太漂亮......

盯着式子发了一会儿呆不知从何入手, 觉得没什么前途, 就学习一下题解......

它有点像范德蒙德卷积. 但是不等于定值......正如我们把一个数列倒过来, 把点积转化为卷积跑FFT. 组合数有对称性, 倒过来很方便:

向成功迈出第一步.

组合数求和没有闭形式. 就像遇到NPC问题一样, 我们得借助题目中的特殊条件, 这里是0 <= a-b <= 10^4, 也就是说, 不会相差太大.

由对称性, 是好求的:

注意特判. 当时, .

其余项暴力求. 可以考虑这个式子:

当然, 前提是我们可以快速提出组合数里的2和5. 根据中国剩余定理, 只需分别考虑. 简单起见, 我们考虑阶乘.

之前在网上学的扩展Lucas是单次询问的. 事实上, 有至少两种方法能减少一个log: - 做快速幂的底数相同, 合并在一起即可. - 根据高斯泛化的威尔逊定理, 非即 , 取决于模数是否有原根. 今天看Tangjz的文章才知道......VW神犇几个月前就告诉过我这篇文章, 但是感觉有点复杂, 就没认真看......( T﹏T )

启发: - 碰到奇怪的式子, 可以考虑打表, 考虑特殊情形, 联想熟悉的公式. - 把和式写成的形式可能比更能带来灵感. - . - 强行构造~ - 盯着式子发呆是最没前途的......应该总能找到事干啊......

这道题的难点主要在于数学上的变形. 把两个简化成一个 . 把和式拆成两部分.

并不需要什么特殊的姿势......需要一点经验或灵感.

实现时遇到的问题: - 没有特判 a=b. - 我的rep宏, 循环变量是int, 而这题需要long long. - 没有管计算过程中出现的负数, 打算最后再处理. 但是exgcd这里模数为负会有点问题......

typedef long long ll;

void exgcd(int a, int b, int& x, int& y)
{
	if (b)
		exgcd(b, a%b, y, x), y -= a/b*x;
	else
		x = 1, y = 0;
}

ll fpm(ll x, ll n, ll m)
{
	ll y = 1;
	for (; n; n >>= 1, (x *= x) %= m)
		if (n & 1)
			(y *= x) %= m;
	return y;
}

inline int inverse(int x, int n)
{
	int a, b;
	exgcd(x, n, a, b);
	return a;
}

struct Num
{
	static int p, e, q, f[1953125 + 5], pp[10];
	static bool flag;
	
	int v, k;
	
	Num(): v(1), k(0) {}
	Num(ll x)
	{
		k = 0;
		while (x % p == 0) x /= p, ++k;
		v = x % q;
	}
	Num(int v, int k): v(v), k(k) {}
	
	static void init(int _p, int _e)
	{
		pp[0] = 1;
		p = _p, e = _e;
		rep (i, 1, e+1) pp[i] = pp[i-1] * p;
		q = pp[e];
		flag = (p & 1) || q == 4;
		f[0] = 1;
		rep (i, 1, q) f[i] = 1LL * f[i-1] * (i % p ? i : 1) % q;
	}
	Num operator*(const Num& o) const
	{
		return Num(1LL * v * o.v % q, k + o.k);
	}
	Num operator/(const Num& o) const
	{
		return Num(1LL * v * inverse(o.v, q) % q, k - o.k);
	}
	bool operator==(const Num& o) const
	{
		return (v-o.v) % q == 0 && k == o.k;
	}
	static Num fac(ll n)
	{
		if (!n) return Num();
		Num ret = fac(n/p) * Num(1, n/p);
		if (flag && (n/q & 1)) ret = ret * Num(-f[n % q], 0);
		else ret = ret * Num(f[n % q], 0);
		return ret;
	}
	int to_int()
	{
		return k < e ? 1LL * v * pp[k] % q : 0;
	}
} half;

int Num::p, Num::e, Num::q, Num::f[1953125 + 5], Num::pp[10];
bool Num::flag;

struct Qr
{
	ll a, b;
	int k, x, y;

	int solve(int p, int e, int q)
	{
		ll s = a+b, ans = fpm(2, s-1, q), m = s/2;
		Num C = Num::fac(s) / (Num::fac(m) * Num::fac(s-m));
		if (a == b) return (ans - (half * C).to_int()) % q;
		if (!(s & 1)) (ans += (half * C).to_int()) %= q;
		for (ll i = m+1; i < a; ++i)
		{
			C = C * Num(s-i+1) / Num(i);
			(ans += C.to_int()) %= q;
		}
		return ans;
	}
} Q[10];

int top, p10[10];

int main()
{
	while (scanf("%lld%lld%d", &Q[top].a, &Q[top].b, &Q[top].k) == 3) ++top;

	Num::init(2, 9);
	half = Num(1) / Num(2);
	rep (i, 0, top) Q[i].x = Q[i].solve(2, 9, Num::pp[9]);

	Num::init(5, 9);
	half = Num(1) / Num(2);
	rep (i, 0, top) Q[i].y = Q[i].solve(5, 9, Num::pp[9]);
	
	p10[0] = 1;
	rep (i, 1, 10) p10[i] = p10[i-1] * 10;
	rep (i, 0, top)
	{
		ll ans = (1LL * Q[i].x * 212890625 + 1LL * Q[i].y * 787109376) % p10[Q[i].k];
		printf("%0*lld\n", Q[i].k, (ans + p10[Q[i].k]) % p10[Q[i].k]);
	}
	
	return 0;
}