题意#

有 $n$ 件礼物，要送给 $m$ 个人，其中送给第 $i$ 个人 $w_i$ 件。

求送礼物的方案数，对 $P$ 取模。

两个方案不同，当且仅当存在某个人在这两种方案中收到的礼物数量不同。

$1\leq n\leq 10^9$ ， $1\leq m\leq 5$ ， $\leq w_i\leq P\leq 10^9$ .

令 $P=\prod_{i=1}^{t}p_i^{c_i}$ ，则 $1\leq p_i^{c_i}\leq 10^5$ .

题解#

\operatorname{Ans} = \binom{n}{w_1}\binom{n-w_1}{w_2}\binom{n-w1-w2}{w3}\cdots\binom{n-w1-w2-w3-w4}{w5}\bmod P

因为 $P$ 不一定是质数，扩展卢卡斯求解即可。

代码#

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10, MAXM = 6;
int p, n, m;
int w[MAXM], sum[MAXM];
int a[MAXN], b[MAXN], cnt = 1; //余数，模数
int power(int x, int k, int p) {
    int ans = 1;
    while(k) {
        if(k & 1) ans = (ans * x) % p;
        k >>= 1;
        x = (x * x) % p;
    }
    return ans;
}
int ExGcd(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    int r = ExGcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return r;
}
int inv(int a, int p) {
    int x, y;
    ExGcd(a, p, x, y);
    return (x % p + p) % p;
}
int fac(int n, int p, int pk) {
    if(n == 0)return 1;
    int ans = 1;
    for(int i = 1; i < pk; i++) {
        if(i % p != 0) {
            ans = ans * i % pk;
        }
    }
    ans = power(ans, n / pk, pk);
    for(int i = 1; i <= n % pk; i++) {
        if(i % p != 0) {
            ans = ans * i % pk;
        }
    }
    return ans * fac(n / p, p, pk) % pk;
}
int C(int n, int m, int p, int pk) { //pk=p^k，求(C_n^m)%(p^k)
    int fac1 = fac(n, p, pk), fac2 = fac(m, p, pk), fac3 = fac(n - m, p, pk);
	int k = 0;
    for(int i = n; i; i /= p)
		k += i / p;
    for(int i = m; i; i /= p)
		k -= i / p;
    for(int i = n - m; i; i /= p)
		k -= i / p;
    return fac1 * inv(fac2, pk) % pk
				* inv(fac3, pk) % pk
				* power(p, k, pk) % pk;
}
int CRT() {
    int M = 1, ans = 0;
    for(int i = 1; i <= cnt; i++)
        M *= b[i];
    for(int i = 1; i <= cnt; i++) {
        int add = a[i] * (M / b[i]) % M * inv(M / b[i], b[i]) % M;
        ans = (ans + add) % M;
    }
    return ans;
}
int ExLucas(int n, int m, int p) {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    cnt = 0;
    for(int i = 2; i * i <= p; i++) {
        int pk = 1;
        while(p % i == 0) {
            pk *= i;
            p /= i;
        }
        if(pk > 1) {
            b[++cnt] = pk;
            a[cnt] = C(n, m, i, pk);
        }
    }
    if(p > 1) {
        b[++cnt] = p;
        a[cnt] = C(n, m, p, p);
    }
    return CRT();
}
signed main() {
    scanf("%lld%lld%lld", &p, &n, &m);
    for(int i = 1; i <= m; i++)
		scanf("%lld", &w[i]);
    for(int i = 1; i <= m; i++)
        sum[i] = sum[i - 1] + w[i];
    if(sum[m] > n){
        cout << "Impossible";
        return 0;
    }
    int ans = 1;
    for(int i = 1; i <= m; i++) {
        ans = (ans * ExLucas(n - sum[i - 1], w[i], p)) % p;
    }
    cout << ans << endl;
    return 0;
}

cpp

【洛谷–P2183】[国家集训队]礼物

题意#

题解#

代码#