AT_abc483_g.Qualification

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given integers N,KN,K. It is guaranteed that the given integers satisfy K≤N2\displaystyle K \le \frac N2.

For permutations P=(P1,P2,…,PN),Q=(Q1,Q2,…,QN)P=(P_1,P_2,\ldots,P_N),Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,…,N)(1,2,\ldots,N), define f(P,Q)f(P,Q) as follows:

NN people, person 11 through person NN, participated in 22 contests, contest A and contest B. Person ii (1≤i≤N)(1\le i\le N) placed PiP_i-th in contest A and QiQ_i-th in contest B.

Consider choosing 2K2K of these NN people by the following 22 selection methods.

  • Method ①: Choose the KK people with the best ranks in contest A. Then, among the N−KN-K people not yet chosen, choose the KK people with the best ranks in contest B.
  • Method ②: Choose the KK people with the best ranks in contest B. Then, among the N−KN-K people not yet chosen, choose the KK people with the best ranks in contest A.

Let f(P,Q)f(P,Q) be the number of people who are chosen by method ① but not chosen by method ②.

There are N!2N!^2 pairs (P,Q)(P,Q) of permutations of (1,2,…,N)(1,2,\ldots,N). Find the sum of f(P,Q)f(P,Q) over all of them, modulo 998244353998244353.

You are given TT test cases; solve each of them.

给定整数 N,KN,K。保证所给整数满足 K≤N2\displaystyle K \le \frac N2。

对于 (1,2,…,N)(1,2,\ldots,N) 的两个排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N) 与 Q=(Q1,Q2,…,QN)Q=(Q_1,Q_2,\ldots,Q_N),定义函数 f(P,Q)f(P,Q) 如下:

有 NN 个人,编号为 11 至 NN,参加了两场竞赛:竞赛 A 和竞赛 B。其中第 ii 个人(1≤i≤N1\le i\le N)在竞赛 A 中获得第 PiP_i 名,在竞赛 B 中获得第 QiQ_i 名。

考虑从这 NN 个人中按以下两种方式各选出 2K2K 人:

  • 方法 ①:先选出竞赛 A 中排名最靠前的 KK 人;然后在剩余未被选中的 N−KN-K 人中,再选出竞赛 B 中排名最靠前的 KK 人。
  • 方法 ②:先选出竞赛 B 中排名最靠前的 KK 人;然后在剩余未被选中的 N−KN-K 人中,再选出竞赛 A 中排名最靠前的 KK 人。

定义 f(P,Q)f(P,Q) 为:被方法 ① 选中但未被方法 ② 选中的人数。

共有 N!2N!^2 对 (P,Q)(P,Q)(即 (1,2,…,N)(1,2,\ldots,N) 的所有排列对)。请计算所有这些对 (P,Q)(P,Q) 对应的 f(P,Q)f(P,Q) 之和,并对 998244353998244353 取模。

你将得到 TT 组测试数据,请对每组数据求解。

输入格式

The input is given from Standard Input in the following format:

TT
case1\text{case}_1
case2\text{case}_2
⋮\vdots
caseT\text{case}_T

Each test case is given in the following format:

NN KK

输入从标准输入给出,格式如下:

TT
case1\text{case}_1
case2\text{case}_2
⋮\vdots
caseT\text{case}_T

每个测试用例的格式如下:

NN KK

输出格式

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 11-st test case.

For example, when P=(2,1,3),Q=(3,1,2)P=(2,1,3),Q=(3,1,2), the people chosen by method ① are persons 22 and 33, and the people chosen by method ② are persons 11 and 22. Therefore, f(P,Q)=1f(P,Q)=1 for this pair P,QP,Q.

There are 66 pairs (P,Q)(P,Q) with f(P,Q)=1f(P,Q)=1, and f(P,Q)=0f(P,Q)=0 holds for the remaining 3030 pairs (P,Q)(P,Q). Therefore, the answer is 6×1+30×0=66\times 1+30\times 0=6.

Constraints

  • 1≤T≤2×1051\le T\le 2\times 10^5
  • 2≤N≤1062\le N\le 10^6
  • 1≤K≤N2\displaystyle 1\le K \le \frac N2
  • The sum of NN over all test cases is at most 10610^6.
  • All input values are integers.

样例 1 解释:
考虑第 11 个测试用例。

例如,当 P=(2,1,3),Q=(3,1,2)P=(2,1,3),Q=(3,1,2) 时,方法①选出的人为第 22 号和第 33 号人员,方法②选出的人为第 11 号和第 22 号人员。因此,对这一对 (P,Q)(P,Q),有 f(P,Q)=1f(P,Q)=1。

满足 f(P,Q)=1f(P,Q)=1 的 (P,Q)(P,Q) 共有 66 对,其余 3030 对 (P,Q)(P,Q) 均满足 f(P,Q)=0f(P,Q)=0。因此,答案为 6×1+30×0=66\times 1+30\times 0=6。

限制条件

  • 1≤T≤2×1051\le T\le 2\times 10^5
  • 2≤N≤1062\le N\le 10^6
  • 1≤K≤N2\displaystyle 1\le K \le \frac N2
  • 所有测试用例的 NN 之和不超过 10610^6。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页