AT_abc483_g.Qualification
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given integers N,K. It is guaranteed that the given integers satisfy K≤2N.
For permutations P=(P1,P2,…,PN),Q=(Q1,Q2,…,QN) of (1,2,…,N), define f(P,Q) as follows:
N people, person 1 through person N, participated in 2 contests, contest A and contest B. Person i (1≤i≤N) placed Pi-th in contest A and Qi-th in contest B.
Consider choosing 2K of these N people by the following 2 selection methods.
- Method ①: Choose the K people with the best ranks in contest A. Then, among the N−K people not yet chosen, choose the K people with the best ranks in contest B.
- Method ②: Choose the K people with the best ranks in contest B. Then, among the N−K people not yet chosen, choose the K people with the best ranks in contest A.
Let f(P,Q) be the number of people who are chosen by method ① but not chosen by method ②.
There are N!2 pairs (P,Q) of permutations of (1,2,…,N). Find the sum of f(P,Q) over all of them, modulo 998244353.
You are given T test cases; solve each of them.
给定整数 N,K。保证所给整数满足 K≤2N。
对于 (1,2,…,N) 的两个排列 P=(P1,P2,…,PN) 与 Q=(Q1,Q2,…,QN),定义函数 f(P,Q) 如下:
有 N 个人,编号为 1 至 N,参加了两场竞赛:竞赛 A 和竞赛 B。其中第 i 个人(1≤i≤N)在竞赛 A 中获得第 Pi 名,在竞赛 B 中获得第 Qi 名。
考虑从这 N 个人中按以下两种方式各选出 2K 人:
- 方法 ①:先选出竞赛 A 中排名最靠前的 K 人;然后在剩余未被选中的 N−K 人中,再选出竞赛 B 中排名最靠前的 K 人。
- 方法 ②:先选出竞赛 B 中排名最靠前的 K 人;然后在剩余未被选中的 N−K 人中,再选出竞赛 A 中排名最靠前的 K 人。
定义 f(P,Q) 为:被方法 ① 选中但未被方法 ② 选中的人数。
共有 N!2 对 (P,Q)(即 (1,2,…,N) 的所有排列对)。请计算所有这些对 (P,Q) 对应的 f(P,Q) 之和,并对 998244353 取模。
你将得到 T 组测试数据,请对每组数据求解。
输入格式
The input is given from Standard Input in the following format:
T
case1
case2
⋮
caseT
Each test case is given in the following format:
N K
输入从标准输入给出,格式如下:
T
case1
case2
⋮
caseT
每个测试用例的格式如下:
N K
输出格式
Print the answers to the test cases in order, separated by newlines.
按顺序输出测试用例的答案,各答案之间用换行符分隔。
输入输出样例
输入#1
4 3 1 6 3 9 2 483 101
输出#1
6 0 982675409 845255482
说明/提示
Sample 1 Explanation:
Consider the 1-st test case.
For example, when P=(2,1,3),Q=(3,1,2), the people chosen by method ① are persons 2 and 3, and the people chosen by method ② are persons 1 and 2. Therefore, f(P,Q)=1 for this pair P,Q.
There are 6 pairs (P,Q) with f(P,Q)=1, and f(P,Q)=0 holds for the remaining 30 pairs (P,Q). Therefore, the answer is 6×1+30×0=6.
Constraints
- 1≤T≤2×105
- 2≤N≤106
- 1≤K≤2N
- The sum of N over all test cases is at most 106.
- All input values are integers.
样例 1 解释:
考虑第 1 个测试用例。
例如,当 P=(2,1,3),Q=(3,1,2) 时,方法①选出的人为第 2 号和第 3 号人员,方法②选出的人为第 1 号和第 2 号人员。因此,对这一对 (P,Q),有 f(P,Q)=1。
满足 f(P,Q)=1 的 (P,Q) 共有 6 对,其余 30 对 (P,Q) 均满足 f(P,Q)=0。因此,答案为 6×1+30×0=6。
限制条件
- 1≤T≤2×105
- 2≤N≤106
- 1≤K≤2N
- 所有测试用例的 N 之和不超过 106。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?