自动搬运

查看原文

来自洛谷，原作者为

	Pursuewind 等风来，不如追风去 || 初一 OIER || qq:2829259510

搬运于2025-08-24 22:57:24，当前版本为作者最后更新于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}$。

所以输出

$$\left(\sum\limits_{k=1}^m \sum\limits_{i=1}^n k! \times C_{n-i+m-2}^{m-2}\right) \bmod P $$

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

$$\left(\sum\limits_{k=1}^m \sum\limits_{i=1}^n k! \times C_{n-i+m-2}^{m-2}\right) \bmod P $$$$=\left(\sum\limits_{k=1}^m k! \left(\sum\limits_{i=1}^n C_{n-i+m-2}^{m-2}\right) \right)\bmod P $$

前面的 $\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;
}