Solution - P10380

Pursuewind · 2024-05-01 22:20:22 · 题解

遇到这种题，首先应该考虑拆贡献。

考虑当第 k 堆的元素数量为 i 时，它有多少分法。

此时分法的数量相当于把 n-i 个元素分为 m-1 组的方案数，隔板法可知方案数为 C_{n-i+m-2}^{m-2} 种。

贡献等于方案乘权值，即 k! \times C_{n-i+m-2}^{m-2}。

所以输出

但是这样是 O(nm) 的，考虑优化。

前面的 \sum\limits_{k=1}^m k! 可以前缀和预处理出，后面的组合数可以用 Lucas 定理求得。

/*
往第 i（1 <= i <= m）位填 j（0 <= j <= n） 的方案数有 C(n-j+m-2,m-2)
贡献为 i!*C(n-j+m-2,m-2) 
*/ 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m, P;
int fac[N], inv[N], a[N], ans = 0;
int sum[N];
int qpow(int a, int b){
    int res = 1, base = a;
    while (b){
        if (b & 1) res *= base;
        base *= base;
        res %= P;
        base %= P;
        b >>= 1;
    }
    return res;
}
int C(int n, int m){
    return fac[n] * inv[n - m] % P * inv[m] % P;
}
int Lucas(int n, int m){
    if (m == 0) return 1;
    return Lucas(n / P, m / P) * C(n % P, m % P) % P;
}
signed main(){
    cin >> n >> m >> P;
    fac[0] = fac[1] = inv[0] = inv[1] = sum[1] = 1;
    for (int i = 2; i <= N - 5; i ++){
        fac[i] = fac[i - 1] * i % P;
        sum[i] = (sum[i - 1] + fac[i]) % P;
        inv[i] = (P - P / i) * inv[P % i] % P;
    }
    for (int i = 1; i <= N - 5; i ++){
        inv[i] = inv[i - 1] * inv[i] % P;
    }
    if (m == 1){
        cout << n % P << "\n";
        return 0;
    }
//  cout << sum[m] << "\n";
//  for (int i = 1; i <= m; i ++){
        for (int j = 1; j <= n; j ++){
            int now = Lucas(m - 2 + n - j, m - 2);
            ans += (sum[m] * j % P * now % P);
            ans %= P;
//          cout << ans << " ";
        }
//      cout << "\n";
//  }
    cout << ans % P << "\n";
    return 0;
}