首页 > 代码库 > WA...

WA...

//组合数取模 #include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxM = 10 + 5, MaxPi = 100000 + 5;int n, m, Top;int W[MaxM], Ci[MaxPi], Pi[MaxPi], Phi[MaxPi], PiCi[MaxPi]; typedef long long LL;LL P, Q, Ans, Sum;LL f[MaxPi], MI[MaxPi], PI[MaxPi];;LL Pow(LL a, LL b, LL Mod) {	a %= Mod; b %= Mod;	LL ret = 1, f = a;	while (b) {		if (b & 1) {			ret *= f;			ret %= Mod;		}		b >>= 1;		f *= f;		f %= Mod;	}	return ret;}struct ES {	LL u, t;};ES Solve(int num, int Pi_e, int PiCi_e) {	ES ret;	ret.u = 0;	ret.t = 1;	while (num) {		ret.u += num / Pi_e;		ret.t *= Pow(f[PiCi_e - 1], num / PiCi_e, PiCi_e);		ret.t %= PiCi_e;		ret.t *= f[num % PiCi_e];		ret.t %= PiCi_e;		num /= Pi_e;	}	return ret;}LL C1(int a, int b, int Pi_e, int PiCi_e, int Phi_e) {	f[0] = 1; f[1] = 1;	for (int i = 2; i <= PiCi_e - 1; i++) {		if (i % Pi_e == 0) f[i] = f[i - 1];		else f[i] = f[i - 1] * i % PiCi_e;	}	LL ret, uu, t1, t2, t3;	ES e1, e2, e3;	e1 = Solve(a, Pi_e, PiCi_e);	e2 = Solve(a - b, Pi_e, PiCi_e);	e3 = Solve(b, Pi_e, PiCi_e);	uu = e1.u - (e2.u + e3.u);	t1 = e1.t; t2 = e2.t; t3 = e3.t;	ret = Pow(Pi_e, uu, PiCi_e);	ret *= t1; ret %= PiCi_e;	ret *= Pow(t2, Phi_e - 1, PiCi_e); ret %= PiCi_e;	ret *= Pow(t3, Phi_e - 1, PiCi_e); ret %= PiCi_e;	return ret;}LL C2(int a, int b) {	LL ret; 	ret = 0;	for (int i = 1; i <= Top; i++) {		ret += (C1(a, b, Pi[i], PiCi[i], Phi[i]) * ((MI[i] * PI[i]) % P)) % P;		ret %= P;	}	return ret;}int main() {	cin >> P >> n >> m;	Sum = 0;	for (int i = 1; i <= m; i++) {		scanf("%d", &W[i]);		Sum += (LL)W[i];	}	if (Sum > n) {		printf("Impossible\n");		return 0;	}	Top = 0;	Q = P;	int SQRTQ = (int)sqrt(Q * 1.0);	for (int i = 2; i <= SQRTQ; i++) {		if (Q % i != 0) continue;		Pi[++Top] = i;		PiCi[Top] = 1;		Ci[Top] = 0;		while (Q % i == 0) {			++Ci[Top];			PiCi[Top] *= i;			Q /= i;		}		Phi[Top] = PiCi[Top] / i * (i - 1);		MI[Top] = P / PiCi[Top];		PI[Top] = Pow(MI[Top], Phi[Top] - 1, PiCi[Top]); 	}	if (Q > 1) {		Pi[++Top] = Q;		PiCi[Top] = Q;		Ci[Top] = 1;		Phi[Top] = Q - 1;		MI[Top] = P / PiCi[Top];		PI[Top] = Pow(MI[Top], Phi[Top] - 1, PiCi[Top]); 	}	Ans = 1;	for (int i = 1; i <= m; i++) {		Ans *= C2(n, W[i]);		Ans %= P;		n -= W[i];	}	cout << Ans << endl;//	printf("%I64d\n", C2(n, m));	return 0;}

  

WA...