随机红包

题目链接：luogu P6130

题目大意

把一个数 1 分成 n 份，求第 k 小的期望大小，多次询问。

思路

首先考虑最小的期望大小，那假设最小的是 \(x\)，剩下的都大于 \(x\)。
那我们把剩下的都减去 \(x\)，就相当于在 \(1-nx\) 的长度上分成 \(n-1\) 份。
那我们有：\(P(L_{\min}\geqslant x)=(1-nx)^{n-1}\)
那期望就是把它积分一下：
\(E(L_{min})=\int_0^{\frac{1}{n}}P(L_{min}\geqslant x)dx\)
\(=\int_0^{\frac{1}{n}}(1-nx)^{n-1}dx\)
\(=\frac{1}{n}\int_0^{1}(1-x)^{n-1}dx\)
\(=\frac{1}{n}\int_0^1 x^{n-1}dx\)（换元一下，\(x\rightarrow n-x\)）
\(=\dfrac{1}{n^2}\)

然后考虑求第二小。
那就是类似的想法，把 \(1\) 减去 \(nx\)，然后里面 \(n-1\) 个选最小。
那就是：\(E(L_{\min})+\dfrac{1-nE(L_{\min})}{(n-1)^2}\)
化简可以得到的是：\(\dfrac{1}{n}(\dfrac{1}{n}+\dfrac{1}{n-1})\)

然后第三小同样的方法：
\(E(L_{2})+\dfrac{1-nE(L_{\min})-(n-1)(E(L_2)-E(L_{\min}))}{(n-2)^2}=\dfrac{1}{n}(\dfrac{1}{n}+\dfrac{1}{n-1}+\dfrac{1}{n-2})\)

找规律或者推一推式子都会发现第 \(k\) 小的答案是：
\(\dfrac{1}{n}\sum\limits_{i=1}^k\dfrac{1}{n-i+1}\)

然后直接预处理 \(\dfrac{1}{x}\) 前缀和就可以快速 \(O(1)\) 回答了。

代码

#include<cstdio>
#define mo 998244353

using namespace std;

const int N = 1e7 + 1000;
int n, k, jc[N], inv[N], invs[N], ans;

int add(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int dec(int x, int y) {return x < y ? x - y + mo : x - y;}
int mul(int x, int y) {return 1ll * x * y % mo;}

int sum(int l, int r) {
	if (!l) return invs[r];
	return dec(invs[r], invs[l - 1]);
}

void work() {
	scanf("%d %d", &n, &k);
	ans ^= mul(inv[n], sum(n - k + 1, n));
}

int main() {
	jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = mul(jc[i - 1], i);
	inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = mul(inv[mo % i], mo - mo / i);
	invs[0] = 1; for (int i = 1; i < N; i++) invs[i] = add(invs[i - 1], inv[i]);
	
	int T; scanf("%d", &T);
	while (T--) work();
	printf("%d", ans);
	
	return 0;
}