Luogu – P2183 – [国家集训队]礼物

题意

有 $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;
}

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇