首页 > 代码库 > 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...
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。