#2120. 随机立方体
随机立方体
随机立方体
题目描述
第一试随机立方体(cube) IOI 2019 中国国家队选拔 随机立方体(cube) 【题目描述】 有一个n ∗m ∗l 的立方体,立方体中每个格子上都有一个数,如果某个格子上的数 比三维坐标.至.少.有.一.维相同的其他格子上的数都要大的话,我们就称它是极大的。 现在将1 ∼n ∗m ∗l 这n ∗m ∗l 个数等概率随机填入n ∗m ∗l 个格子(即任意数字 出现在任意格子上的概率均相等),使得每个数恰出现一次,求恰有k 个极大的数的概 率。答案对998244353 (一个质数)取模。 【输入格式】 从文件cube.in 中读入数据。 输入包含多组数据。输入第一行包含一个正整数T,表示数据组数。 接下来T 行,每行一组数据,包含4 个正整数n, m, l, k,表示一次询问。 【输出格式】 输出到文件cube.out 中。 对于每次询问,输出一行一个整数,表示答案对998244353 取模的余数。 可以证明,答案一定为有理数。设其为a/b(a 和b 为互质的正整数,数据保证b 不为998244353 的倍数),则你需要保证输出的数x 满足0 ≤x < 998244353 且a ≡bx (mod 998244353)。可以证明这样的x 唯一存在。 【样例1 输入】 5 1 1 1 1 2 2 2 1 7 8 9 3 123 456 789 1 1000 1000 1000 10 【样例1 输出】 1 142606337 736950806 246172965 189652652 第2 页 共9 页 第一试随机立方体(cube) IOI 2019 中国国家队选拔 【样例2】 见选手目录下的cube/cube2.in 与cube/cube2.ans。 【测试数据约定】 对于10% 的数据,n, m ≤2,l ≤3,k = 1。 对于30% 的数据,n, m, l, k ≤12。 对于40% 的数据,n, m, l ≤100。 对于50% 的数据,n, m, l ≤1000。 对于60% 的数据,n, m, l ≤100000,其中有占全部数据30% 的数据保证k = 1。 对于80% 的数据,n, m, l ≤1000000,其中有占全部数据40% 的数据保证k = 1。 对于100% 的数据,1 ≤n, m, l ≤5000000,1 ≤k ≤100,1 ≤T ≤10, 其中有50% 的数据保证k = 1。 第3 页 共9 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5
1 1 1 1
2 2 2 1
7 8 9 3
123 456 789 1
1000 1000 1000 10
1
142606337
736950806
246172965
189652652
样例 2
10
4975401 4951343 4803566 22
4499697 4989534 4995301 89
4960387 4800714 4985451 20
4549943 4925900 4582735 36
3010525 4611932 4998770 67
4980964 4865325 4531707 55
2953628 4962026 4999540 52
4599954 4988700 4817773 75
4981351 4950027 4852696 16
4695981 4993997 4953978 2
856105281
423884937
154402492
813209966
683750161
337149076
838552619
849850633
605653899
384868262