人人人数

题目链接：YBT2023寒假Day4 B

题目大意

随机生成一个长度为 m 且每个元素都是 1~n 的整数单调不降序列，问你这个序列的众数的期望出现次数是多少。
（随机是所有满足条件的序列中概率都一样）

思路

首先这个单调不降序列，那确定了每个数的个数的话，数的顺序是固定的。
也就是不用考虑顺序。

然后考虑它可以转化为众数出现 \(i\) 的概率乘 \(i\)。
然后就是对于每个 \(i\) 众数出现次数 \(\geqslant i\) 的概率的和。
然后再容斥一下就是 \(m-\) 众数出现次数小于 \(i\) 的概率的和。

对于这个出现次数小于 \(i\)，考虑再容斥，有 \(k\) 个数的出现次数 \(\geqslant i\)。（会发现需要满足 \(ik\leqslant m\)，那这里两个枚举的总复杂度就是 \(m\log m\) 级别的）
于是考虑把这 \(k\) 数的出现次数减去 \(i\)，那就变回了完全没有限制的 \(m-ik\) 个值域是 \(n\)。
那完全没有限制我们可以用插板法：\(\binom{n+m-ik-1}{m-ik}\)

那么式子就是：
\(\dfrac{\sum\limits_{i=1}^m(1-\sum\limits_{k=0}^{\left\lfloor\frac{m}{i}\right\rfloor}(-1)^{k}\binom{n}{k}\binom{n+m-ik-1}{m-ik})}{{\binom{m}{n+m-1}}}\)

预处理 \(\binom{n}{i}\) 和 \(\binom{i}{n+i-1}\) 即可。

代码

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

const int N = 4e5 + 100;
ll mo, C1[N], C2[N], jc[N], inv[N], invs[N];
int m, n;

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo;
		x = x * x % mo; y >>= 1; 
	}
	return re;
}

ll slove(int i) {
	ll re = 0;
	for (int j = 0, zf = 1; j <= m / i; j++, zf = mo - zf)
		(re += zf * C1[j] % mo * C2[m - i * j] % mo) %= mo;
	re = re * ksm(C2[m], mo - 2) % mo;
	return re;
}

void slove() {
	scanf("%d %d", &m, &n);
	C1[0] = 1; for (int i = 1; i <= m; i++) C1[i] = C1[i - 1] * inv[i] % mo * (n - i + 1) % mo;
	C2[0] = 1; for (int i = 1; i <= m; i++) C2[i] = C2[i - 1] * inv[i] % mo * (n + i - 1) % mo;
	ll ans = m;
	for (int i = 1; i <= m; i++) (ans += mo - slove(i)) %= mo;
	printf("%lld\n", ans);
}

int main() {
	freopen("mode.in", "r", stdin);
	freopen("mode.out", "w", stdout);
	
	int T; scanf("%d %lld", &T, &mo);
	jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = jc[i - 1] * i % mo;
	inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	invs[0] = 1; for (int i = 2; i < N; i++) invs[i] = invs[i - 1] * inv[i] % mo;
	while (T--) slove();
	return 0;
}