#PQJ301x4471. QOJ 301_4471
QOJ 301_4471
第一试随机立方体(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 页