自动搬运

查看原文

来自洛谷，原作者为

	JCY_ Nothing is wasted

搬运于2025-08-24 21:49:04，当前版本为作者最后更新于2022-09-23 09:38:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

更好的阅读体验

神仙题目！！！感谢程老师完成了几乎所有的证明过程。

首先注意到模数是 $2005$，去掉模数似乎很不可做，所以大胆猜测正解依赖模数。

不难发现，把 $n$ 个人分成 $k_1$ 个大小为 $a_1$ 的环，$k_2$ 个大小为 $a_2$ 的环，$\dots$ $k_m$ 个大小为 $a_m$ 的环的方案（$a_1 < a_2 < \dots < a_m$，$k_1, k_2, \dots, k_m>0$，$\sum _{i = 1} ^ m k_i = k$），对答案的贡献是：

$$\frac{n!}{\prod _{i = 1} ^ m a_i! ^ {k_i} \times k_i!}\times \prod _{i = 1} ^ m (a_i - 1)! ^ {k_i}=\frac{n!}{\prod _{i = 1} ^ m a_i ^ {k_i} \times k_i!} $$

设模数为 $p$，不妨令 $p$ 为质数，最后再用中国剩余定理合并答案。下述证明用到了质数的若干性质。现在考察上式模 $p$ 不为 $0$ 的情况下 $\left\{ a_m \right\}$ 和 $\left\{ k_m \right\}$ 具有的性质。

性质一：$a_m \le p$。

考察等号左边的式子。若 $a_m > p$ 则 $(a_m - 1)! ^ {k_m} \equiv 0\ ~ (\text{mod} ~ p)$，上式显然为 $0$。

性质二：$\forall n \ge p$，$a_m=p$。

考察等号右边的式子，记 $h(x)$ 表示 $x$ 含有的质因子 $p$ 的个数。考虑反证法，设 $a_m < p$。此时，$h(n!) > 0$，$h(\prod _{i = 1} ^ m a_i ^ {k_i} \times k_i!) = h(\prod _{i=1} ^ m k_i!) \le h(k!)$。因为 $l \ge 2$，所以 $k \le \lfloor \frac{n}{2} \rfloor$，即 $h(n!) > h(k!) \ge h(\prod _{i = 1} ^ m a_i ^ {k_i} \times k_i!)$，可知原式模意义下为 $0$。

记 $f(x,y)$ 为将 $x$ 个小朋友分成 $y$ 个大小不小于 $l$ 的环的方案数，考察上述性质能推出什么结论。

性质三：记 $q = \lfloor \frac{n}{p} \rfloor$，$f(n,k) \equiv (-1) ^ q \times f(n ~ \text{mod} ~ p, k - q) ~ (\text{mod} ~ p)$。

由性质二，不难递归证明 $n$ 个小朋友一定会分成 $q$ 个大小为 $p$ 的组。考虑这一过程的组合系数，即：

$$\binom{n}{q \times p} \times \frac{\prod _{i = 1} ^ q \binom{i \times p}{p}}{q!} \times (p - 1)! ^ q $$

由威尔逊定理可知，$(p - 1)! ^ q \equiv (-1) ^ q ~ (\text{mod} ~ p)$。

由卢卡斯定理可知，$\binom{n}{q \times p} \equiv \binom{q}{q} \times \binom{n ~ \text{mod} ~ p}{0} \equiv 1 ~ (\text{mod} ~ p)$。

$$\frac{\prod _{i = 1} ^ q \binom{i \times p}{p}}{q!} = \frac{\prod _{i = 1} ^ q i \times \binom{i \times p - 1}{p - 1}}{q!} = \prod _{i = 1} ^ q \binom{i \times p - 1}{p - 1} $$

同样由卢卡斯定理可知，$\prod _{i = 1} ^ q \binom{i \times p - 1}{p - 1} \equiv \prod _{i = 1} ^ q \binom{i - 1}{0} \times \binom{p - 1}{p - 1} \equiv 1 ~ (\text{mod} ~ p)$

所以 $\binom{n}{q \times p} \times \frac{\prod _{i = 1} ^ q \binom{i \times p}{p}}{q!} \times (p - 1)! ^ q \equiv (-1) ^ q ~ (\text{mod} ~ p)$。

所以模 $p$ 意义下的 $f(n,k)$ 可以转化为 $f(n ~ \text{mod} ~ p, k - q)$，注意到转化后合法的 $f(x,y)$ 均满足 $x, y \le 401$，所以可以直接 dp。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k, l;
int f(int x, int y, int mod) {
    static int dp[410][410], chs[410];
    dp[0][0] = 1;
    for (int i = l; i <= x; ++i) {
        chs[i] = 1;
        for (int j = i - l + 1; j < i; ++j) chs[i] = chs[i] * j % mod;
    }
    for (int i = 1; i <= y; ++i) {
        for (int j = i * l; j <= x; ++j)
            dp[i][j] =
                (dp[i - 1][j - l] * chs[j] + dp[i][j - 1] * (j - 1)) % mod;
    }
    return dp[y][x];
}
int solve(int mod) {
    if (l > mod) return 0;
    int q = n / mod, r = n % mod;
    if (q > k || (ll)(k - q) * l > r) return 0;
    int ret = f(r, k - q, mod);
    if (q & 1) ret = (mod - ret) % mod;
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k >> l;
    int t1 = solve(5), t2 = solve(401);
    while (t2 % 5 != t1) t2 += 401;
    cout << t2 << "\n";
    return 0;
}