#S0102. 随机红包

    ID: 312 远端评测题 2000ms 250MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>数论数学乘法逆元概率数值积分luogu

随机红包

题目背景

出题人准备发一个微信红包给一些人,他很好奇如何随机分配里面的钱。

题目描述

出题人蒟蒻的红包里有着 11 块钱,他要把这块钱随机分给 nn 个人。

为了随机,他设计了以下算法进行分配:(用伪代码表示)

a[0]=0,a[n]=1
for i=1 to n-1 do{
    a[i]=rand()
}
sort(a)
for i=1 to n do{
    money[i]=a[i]-a[i-1]
}

这里的 rand() 函数会等概率随机返回一个 [0,1][0,1] 之间的实数值,sort() 函数会将一个数组从小到大排序。

现在,出题人蒟蒻很好奇得到钱数第 kk 少的人得到的钱的期望。

由于他要根据这个值去推算他要发多少个红包,所以他要问你 TT 次。

为了避免精度丢失,答案对 998244353998244353 取模。

为了避免输出量过大,输出所有答案的异或和。

输入格式

本题有多组数据

第一行为整数 TT,表示数据组数。

对于每组数据,一行两个整数 n,kn,k

输出格式

共一行一个整数,表示所有询问的答案的异或和。

3
1 1
2 2
2 1
574619649

提示

【样例解释】

第一个问题,n=k=1n=k=1,答案是 11

第二个问题,较大的数在 [12,1][\dfrac{1}{2},1] 上均匀分布,期望为 34\dfrac{3}{4},取模后为 249561089249561089

第三个问题,较小的数在 [0,12][0,\dfrac{1}{2}] 上均匀分布,期望为 14\dfrac{1}{4},取模后为 748683265748683265

异或和为 574619649574619649


【数据范围】

本题采用捆绑测试

Subtask 1 (4 pts)\text{Subtask 1 (4 pts)}n10n \le 10k=1k=1

Subtask 2 (16 pts)\text{Subtask 2 (16 pts)}n5×103n \le 5 \times 10^3

Subtask 3 (20 pts)\text{Subtask 3 (20 pts)}k=1k=1

Subtask 4 (28 pts)\text{Subtask 4 (28 pts)}n105n \le 10^5

Subtask 5 (32 pts)\text{Subtask 5 (32 pts)}:没有任何额外限制。

对于 100%100\% 的数据,1kn1071 \le k \le n \le 10^71T2×1051 \le T \le 2 \times 10^5