容斥原理+组合数+ Lucas定理
先考虑没有任何限制的情况方案数
即将m个球分到n+1个抽屉里(在原有的n种类型上加一个不使用的情况)
即C(m + n)取m (隔板法可证)
有T个限制的方案可用容斥原理求出, 即
因为n, m 的取值范围为1e9, 而p的范围为1e5
用Lucas定理求组合数,
定义： Lucas(n, m) 为 C n 取m 模p的值
Lucas定理：在模素数p的情况下, Lucas(n, m) = Lucas( n / p, m / p) * Lucas( n % p, m % p)
证明见<关于Lucas定理的证明>
附上代码
#include typedef long long LL; const int MaxT = 20; const int MaxP = 1e5 + 5; int N, T, M, P, b[MaxT], ans; int Fac[MaxP], IE[MaxP]; int pow(int x, int k) { LL res = 1, r = x; for (; k; k >>= 1, r = r * r % P) if (k & 1) res = res * r % P; return res; } LL Lucas(int n, int m) { //Lucas定理求Cn取m if (n < m) return 0; if (n < P && m < P) return (LL)Fac[n] * IE[m] % P * IE[n - m] % P; return Lucas(n / P, m / P) * Lucas(n % P, m % P) % P; } void calc(int x, int sign, int s) { if (x > T) { ans += Lucas(M - s + N, M - s) * sign; ans %= P; return; } calc(x + 1, sign, s); calc(x + 1, -sign, s + b[x] + 1); } int main() { scanf("%d%d%d%d", &N, &T, &M, &P); for (int i = 1; i <= T; ++i) scanf("%d", &b[i]); Fac[0] = 1; for (int i = 1; i < P; ++i) Fac[i] = (LL)Fac[i - 1] * i % P; IE[P - 1] = pow(Fac[P - 1], P - 2); for (int i = P - 1; i; --i) IE[i - 1] = (LL)IE[i] * i % P; calc(1, 1, 0); printf("%d\n", (ans + P) % P); }
