[国家集训队]礼物

Description

Luogu2183
BZOJ2142

Solution

我们可以想象成把这(n)件物品排成一个排列，然后第1个人拿前(w_1)个，第2个人拿之后的(w_2)个，以此类推。由于每个人拿到的东西的是没有顺序的，还要在方案数上除掉(w_i!)，别忘了剩下的物品其实也是没有顺序的，也要除以它们的阶乘。所以答案就是(dfrac{n!}{(n - sum_iw_i)!prod_{i}w_i!})。

直接用扩展lucas的思路算就行。

Code

#include <cstdio>
#include <cmath>

typedef long long LL;

LL n, m, P;
LL w[6], tot;

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

LL pow_mod(LL x, LL p, LL mod) {
	LL ans = 1;
	for (; p; p>>=1, x=x*x%mod) if (p&1) ans = ans * x % mod;
	return ans;
}

LL fac(LL n, LL p, LL pk) {
	if (!n) return 1;
	LL ans = 1;
	for (int i = 2; i <= pk; ++i) if (i%p) ans = ans * i % pk;
	ans = pow_mod(ans, n/pk, pk);
	for (int i = 2; i <= n%pk; ++i) if (i%p) ans = ans * i % pk;
	return ans * fac(n/p, p, pk) % pk;
}

LL inv(LL n, LL mod) {
	LL x, y, d;
	exgcd(n, mod, x, y, d);
	return (x%=mod) < 0 ? x+mod : x;
}

LL CRT(LL b, LL mod) {
	return b*(P/mod)%P*inv(P/mod, mod)%P;
}

LL calc(LL x, LL p) {
	LL k = 0;
	for (; x; x /= p) k += x / p;
	return k;
}

LL C(LL p, LL pk) {
	LL u = fac(n, p, pk), d = inv(fac(n-tot, p, pk), pk);
	for (int i = 1; i <= m; ++i) {
		d = d * inv(fac(w[i], p, pk), pk) % pk;
	}
	LL k = 0;
	k += calc(n, p);
	k -= calc(n-tot, p);
	for (int i = 1; i <= m; ++i) {
		k -= calc(w[i], p);
	}
	return u * d % pk * pow_mod(p, k, pk) % pk;
}

void work() {
	if (tot > n) {
		puts("Impossible");
		return;
	}
	LL ans = 0, tmp = P, pk;
	LL lim = sqrt(P) + 5;
	for (int i = 2; i <= lim; ++i) if (tmp % i == 0) {
		pk = 1;
		while (tmp % i == 0) pk*=i, tmp/=i;
		ans = (ans + CRT(C(i, pk), pk)) % P;
	}
	if (tmp > 1) {
		ans = (ans + CRT(C(tmp, tmp), tmp)) % P;
	}
	printf("%lld
", ans);
}

int main() {
	scanf("%lld%lld%lld", &P, &n, &m);
	for (int i = 1; i <= m; ++i) scanf("%lld", &w[i]), tot += w[i];
	work();
	return 0;
}

Note

其实还有一种等价的答案：(displaystyle{nchoose sum_i w_i}prod_i{sum_{j=i}^nw_jchoose w_i})不过这样要算很多次lucas，比较麻烦，也会比较慢。