小山的元力题解

szh_AK_all · 2024-03-26 20:26:37 · 题解

出题人题解。

同样，对于第一档部分分，直接暴力即可。

正解

既然需要求出每一种分法所贡献的值，不妨求出每一堆所贡献的值。

先考虑第一堆。

显然，可以考虑枚举第一堆的元素数量，即将 i 从 0 枚举到 n，其中 i=0 的情况可以省略。当第一堆的元素数量确定时，它所产生的贡献与方案数有关。

这里的方案数值的是：当第一堆的元素数量为 i 时，总共有多少种分法。

假设有 x 中分法，那么此时所产生的贡献即为：i\times x。

关键在于如何求 x。

由于第一堆的数量已经确定，所以可以转换为这个问题：求将 n-i 个元素分为 m-1 堆的方案数。

这个问题可以用隔板法解决，方案数即为：C_{n-i+m-2}^{m-2}。

第一堆考虑完毕后，在考虑其他堆。

拿第二堆举例，第二堆的元素数量 i 也可以从 0 枚举到 n，且确定第二堆的元素数量后，方案数也为 C_{n-i+m-2}^{m-2}。唯一与第一堆不同的是，它所产生的贡献为：2\times i\times x，x 的含义与上文相同。

同理，第三堆所产生的贡献即为：6\times i\times x。

依此类推，可以用递推的方法求出每一堆所产生的贡献。

注意特判 m=1 的情况。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int jie[2000005];

int qpow(int a, int b, int p) {
    int ans = 1;
    while (b) {
        if (b % 2 == 1)
            ans = ans * a % p;
        a = a * a % p;
        b /= 2;
    }
    return ans % p;
}

int c(int n, int m, int p) {
    if (m > n)
        return 0;
    return jie[n] * qpow(jie[m], p - 2, p) % p * qpow(jie[n - m], p - 2, p) % p;
}

int lucas(int n, int m, int p) {
    if (!m)
        return 1;
    return lucas(n / p, m / p, p) * c(n % p, m % p, p) % p;
}

signed main() {
    int n, m, p;
    cin >> n >> m >> p;
    if (m == 1) {
        cout << n % p;
        return 0;
    }
    int tmp = 0;
    jie[0] = 1;
    for (int i = 1; i <= n + m; i++)
        jie[i] = jie[i - 1] * i % p;
    for (int i = 1; i <= n; i++)
        tmp += i * lucas(n - i + m - 2, m - 2, p), tmp %= p;
    int ans = tmp;
    for (int i = 2; i <= m; i++) {
        tmp = tmp * i % p;
        ans += tmp;
        ans %= p;
    }
    cout << ans;
}