「一本通 6.6 练习 8」礼物

形式化题目

购买 $n$ 件礼物送给 $m$ 个人，第 $i$ 人至少收 $w_i$ 件。求分配方案数模 $P$ （ $P \le 10^9$ ，不保证是素数）；若 $\sum w_i > n$ 则输出 Impossible。

正解

思路

1. 乘法拆解：顺序选人

依次给每个人挑礼物，第 $i$ 人从剩余礼物中选 $w_i$ 件，方案总数为连乘：

\binom{n}{w_1}\binom{n - w_1}{w_2}\cdots\binom{n - w_1 - \cdots - w_{m-1}}{w_m}

每个人挑完即确定（人选有标号、礼物无标号），乘起来就是答案。判无解只需 $\sum w_i > n$ 。

2. 模数是合数：扩展 Lucas

普通 Lucas 只适用于素数模。 $P \le 10^9$ 是合数时，标准做法 exLucas：

把 $P$ 分解为质因数幂 $P = \prod p_i^{k_i}$ （试除到 $\sqrt{P}$ 即可）；
对每个 $p^k$ 单独求 $C(n, m) \bmod p^k$ ；
用 CRT（中国剩余定理） 把各 $p^k$ 下的余数拼回模 $P$ 的唯一解。

3. 求 C(n, m) mod p^k 的关键：抽干 p 因子

$p$ 不再可逆（分母含 $p$ 时逆元不存在），处理分三步：

指数分离：用勒让德公式算出 $C(n,m)$ 中 $p$ 的总指数 $e$ （对 $n!, m!, (n-m)!$ 分别累加 $\lfloor x/p \rfloor + \lfloor x/p^2 \rfloor + \cdots$ 后相减）；
p-free 阶乘：把 $n!$ 中所有 $p$ 的因子抽掉后剩下的部分模 $p^k$ 。利用周期性分块： $1 \dots p^k$ 内与 $p$ 互素的数乘积作为一个"整块"复用，剩余零头单独算；
合成： $C(n,m) \equiv p^e \cdot \text{unit} \pmod{p^k}$ 。若 $p^e$ 已是 $p^k$ 的倍数则直接为 $0$ 。

Python 的 pow(x, -1, pk) 保证模逆元存在（ $x$ 与 $p$ 互素时），支撑 p-free 部分的除法。

4. CRT 合并

模数两两互素，逐个合并方程 res += (a - res) * inv(M, q) * M，把模 $M$ 的解抬升到模 $Mq$ 且对 $q$ 也取到余数 $a$ ，最终 $res \bmod P$ 即答案。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 00:33
# update_at: 2026-10-01 00:33

import sys


def fact_pfree(n: int, p: int, pk: int) -> int:
    """n! 抽掉所有 p 因子后模 pk 的值。

    按 pk 分块：一个完整块 [1..pk] 内与 p 互素的数乘积是常数 block，
    完整块贡献 block^(n//pk)；零头块 [1..n%pk] 单独乘；
    再递归处理 n! 中每隔 p 个数的那一层（其乘积是 (n//p)!）。
    """
    if n == 0:
        return 1
    res = 1
    block = 1
    for i in range(1, pk + 1):
        if i % p:
            block = block * i % pk
    res = pow(block, n // pk, pk)
    for i in range(1, n % pk + 1):
        if i % p:
            res = res * i % pk
    return res * fact_pfree(n // p, p, pk) % pk


def small_comb(n: int, m: int, p: int, pk: int) -> int:
    """C(n, m) 模 pk（pk = p^k）：先算 p 的指数 e，再合成 p^e * 三个 p-free 阶乘。"""
    if m < 0 or m > n:
        return 0
    e = 0  # C(n, m) 里 p 的总指数：(n! 的) - (m! 的) - ((n-m)! 的)
    x = n
    while x:
        x //= p
        e += x
    x = m
    while x:
        x //= p
        e -= x
    x = n - m
    while x:
        x //= p
        e -= x

    if pk // (p ** e) == 0:  # p^e 已是 pk 的倍数，整个 C(n,m) ≡ 0 (mod pk)
        return 0

    unit = (
        fact_pfree(n, p, pk)
        * pow(fact_pfree(m, p, pk), -1, pk)
        % pk
        * pow(fact_pfree(n - m, p, pk), -1, pk)
        % pk
    )
    return pow(p, e, pk) * unit % pk


def crt(rests: list[int], mods: list[int]) -> int:
    """中国剩余定理：模数两两互素，逐个合并余数方程，返回模 ∏mods 下的解。"""
    M, res = 1, 0
    for a, q in zip(rests, mods):
        res += (a - res) * pow(M, -1, q) % q * M  # 把模 M 的解抬到模 M*q 且对 q 也对上 a
        M *= q
    return res % M


def factorize(x: int) -> list[tuple[int, int]]:
    """分解质因数，返回 [(质数 p, p 的幂 pk)]；P ≤ 1e9，试除到 √x 即可。"""
    res: list[tuple[int, int]] = []
    d = 2
    while d * d <= x:
        if x % d == 0:
            pk = 1
            while x % d == 0:
                x //= d
                pk *= d
            res.append((d, pk))
        d += 1
    return res + [(x, x)] if x > 1 else res


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    P, n, m = next(data), next(data), next(data)
    weights = [next(data) for _ in range(m)]

    if sum(weights) > n:  # 礼物要发完，总数超出 n 就没有可行方案
        print('Impossible')
        return

    # P = ∏ p_i^{c_i}：在每条 C(剩余人数, w_i) 上分别取模，再用 CRT 拼回模 P。
    factors = factorize(P)
    primes, powers = [p for p, _ in factors], [pk for _, pk in factors]
    rests = [1] * len(factors)
    for w in weights:
        rests = [r * small_comb(n, w, p, pk) % pk for r, p, pk in zip(rests, primes, powers)]
        n -= w  # 第 i 个人挑完后，剩余礼物数交给下一个人继续挑
    print(crt(rests, powers))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:04
 * update_at: 2026-10-06 01:04
 */
#include <iostream>
#include <utility>
using namespace std;

typedef long long ll;

// 扩展 Lucas（exLucas）：组合数模合数 P。
// 思路：把 P 分解为质因数幂 p^k，在每条 C(n,m) mod p^k 上分别求值，
// 再用中国剩余定理拼回模 P 的答案。

const int MAXF = 40; // P <= 1e9，不同质因数不超过 10 个，40 足够

ll P;
ll n, m;
ll weight[10]; // weight[i] 表示第 i 个人至少要收到的礼物数

ll prime_arr[MAXF]; // 每个质因数 p
ll pow_arr[MAXF];   // 对应的 p^k
ll rest_arr[MAXF];  // 当前答案在模 p^k 下的余数
int fac_cnt;        // P 的质因数个数

// 求 a 在模 mod 下的逆元，保证 gcd(a, mod) = 1。
ll mod_inv(ll a, ll mod) {
    ll b = mod;
    ll u = 1, v = 0; // u 记录 a 的系数，v 记录 mod 的系数
    // 迭代扩展欧几里得，避免递归
    while (b != 0) {
        ll q = a / b;
        a -= q * b;
        swap(a, b);
        u -= q * v;
        swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

// 快速幂：base^exp mod mod。
ll pow_mod(ll base, ll exp, ll mod) {
    ll res = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

// 计算 n! 抽掉所有 p 因子后得到的数模 pk（pk = p^k）。
// 按 pk 分块：一个完整块 [1..pk] 内与 p 互素的数乘积固定，可整体幂；
// 零头单独乘；再递归处理 n! 中每隔 p 个数的一层，其乘积对应 (n/p)!。
ll fact_pfree(ll n, ll p, ll pk) {
    if (n == 0) return 1 % pk;
    ll block = 1;
    for (ll i = 1; i <= pk; i++) {
        if (i % p != 0) block = block * i % pk;
    }
    ll res = pow_mod(block, n / pk, pk);
    for (ll i = 1; i <= n % pk; i++) {
        if (i % p != 0) res = res * i % pk;
    }
    return res * fact_pfree(n / p, p, pk) % pk;
}

// 计算 C(n, m) mod pk（pk = p^k）。
ll small_comb(ll n, ll m, ll p, ll pk) {
    if (m < 0 || m > n) return 0;

    // 勒让德公式：求 C(n,m) 中 p 的总指数 e = v_p(n!) - v_p(m!) - v_p((n-m)!)
    ll e = 0;
    ll x = n;
    while (x > 0) {
        x /= p;
        e += x;
    }
    x = m;
    while (x > 0) {
        x /= p;
        e -= x;
    }
    x = n - m;
    while (x > 0) {
        x /= p;
        e -= x;
    }

    // 求 pk 中 p 的指数 k，若 e >= k 则结果已是 pk 的倍数
    ll k = 0;
    ll t = pk;
    while (t % p == 0) {
        t /= p;
        k++;
    }
    if (e >= k) return 0;

    // p-free 部分用逆元做除法
    ll unit = fact_pfree(n, p, pk);
    unit = unit * mod_inv(fact_pfree(m, p, pk), pk) % pk;
    unit = unit * mod_inv(fact_pfree(n - m, p, pk), pk) % pk;
    return pow_mod(p, e, pk) * unit % pk;
}

// 把 P 分解为质因数幂，结果存入 prime_arr / pow_arr。
void factorize(ll x) {
    fac_cnt = 0;
    for (ll d = 2; d * d <= x; d++) {
        if (x % d == 0) {
            ll pk = 1;
            while (x % d == 0) {
                x /= d;
                pk *= d;
            }
            prime_arr[fac_cnt] = d;
            pow_arr[fac_cnt] = pk;
            fac_cnt++;
        }
    }
    if (x > 1) {
        prime_arr[fac_cnt] = x;
        pow_arr[fac_cnt] = x;
        fac_cnt++;
    }
}

// 中国剩余定理：模数两两互素，逐个合并余数方程，返回模 ∏pow_arr 下的解。
ll crt_solve(int cnt) {
    ll res = 0;
    ll M = 1;
    for (int i = 0; i < cnt; i++) {
        ll a = rest_arr[i];
        ll q = pow_arr[i];
        ll diff = ((a - res) % q + q) % q;
        ll step = diff * mod_inv(M % q, q) % q;
        res += step * M;
        M *= q;
    }
    return res % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> P;
    cin >> n >> m;
    ll sum_w = 0;
    for (int i = 1; i <= m; i++) {
        cin >> weight[i];
        sum_w += weight[i];
    }

    if (sum_w > n) {
        cout << "Impossible" << '\n';
        return 0;
    }

    // 先分解模数，再在每条组合数上分别对 p^k 取模
    factorize(P);
    for (int i = 0; i < fac_cnt; i++) {
        rest_arr[i] = 1 % pow_arr[i];
    }

    // 依次给第 i 个人从剩余礼物中选 weight[i] 件，方案数相乘
    ll remain = n;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < fac_cnt; j++) {
            ll c = small_comb(remain, weight[i], prime_arr[j], pow_arr[j]);
            rest_arr[j] = rest_arr[j] * c % pow_arr[j];
        }
        remain -= weight[i];
    }

    if (fac_cnt == 0) {
        // P = 1 时任何数都同余于 0
        cout << 0 << '\n';
        return 0;
    }

    cout << crt_solve(fac_cnt) % P << '\n';
    return 0;
}

复杂度

时间复杂度：分解 $P$ 为 $O(\sqrt P)$ ；每个质因数幂的 exLucas 为 $O(p^k + \log n)$ （p-free 分块枚举 $p^k$ 以内互素数），总体对 $P \le 10^9$ 完全可行。
空间复杂度： $O(\log P)$ ，仅存质因数幂表。

总结

本题是 exLucas 标准模板：「组合数连乘 + 合数模」的完整流程——质因数分解、抽干 $p$ 因子、分块 p-free 阶乘、CRT 合并。
与素数模 Lucas（1656 Combination）形成对照：模数不再是素数时，必须在 $p^k$ 下手工处理不可逆的分母。
无解判定 $\sum w_i > n$ 简单但必要；连乘拆解把"多约束分配"化为一串独立组合数。