/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
整数 N,K が与えられます。与えられる整数は \displaystyle K \le \frac N2 を満たすことが保証されます。
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N),Q=(Q_1,Q_2,\ldots,Q_N) に対し、f(P,Q) を以下のように定義します：
人 1 から人 N までの N 人の人がコンテスト A, B の 2 つのコンテストに出場した。人 i (1\le i\le N) はコンテスト A で P_i 位、コンテスト B で Q_i 位であった。
この N 人の中から 2K 人を以下の 2 つの選抜方法で選ぶことを考える。
- ①：コンテスト A で順位の良い K 人を選ぶ。その後、まだ選ばれていない N-K 人のうちコンテスト B で順位の良い K 人を選ぶ。
- ②：コンテスト B で順位の良い K 人を選ぶ。その後、まだ選ばれていない N-K 人のうちコンテスト A で順位の良い K 人を選ぶ。
選抜方法①で選ばれ、選抜方法②で選ばれないような人数を f(P,Q) とする。
(1,2,\ldots,N) の順列の組 (P,Q) は N!^2 通りありますが、それら全てに対する f(P,Q) の総和を 998244353 で割ったあまりを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 2\times 10^5
- 2\le N\le 10^6
- \displaystyle 1\le K \le \frac N2
- 全てのテストケースにおける N の総和は 10^6 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N K
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
入力例 1
4 3 1 6 3 9 2 483 101
出力例 1
6 0 982675409 845255482
1 番目のテストケースについて考えます。
例えば P=(2,1,3),Q=(3,1,2) のとき、選抜方法①で選ばれる人は人 2,3 の 2 人で、選抜方法②で選ばれる人は人 1,2 の 2 人です。したがって、この P,Q に対し f(P,Q)=1 となります。
f(P,Q)=1 となる (P,Q) の組は 6 通りで、残りの 30 通りの (P,Q) の組に対して f(P,Q)=0 が成り立ちます。したがって、答えは 6\times 1+30\times 0=6 となります。
Score : 575 points
Problem Statement
You are given integers N,K. It is guaranteed that the given integers satisfy \displaystyle K \le \frac N2.
For permutations P=(P_1,P_2,\ldots,P_N),Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,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\le i\le N) placed P_i-th in contest A and Q_i-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,\ldots,N). Find the sum of f(P,Q) over all of them, modulo 998244353.
You are given T test cases; solve each of them.
Constraints
- 1\le T\le 2\times 10^5
- 2\le N\le 10^6
- \displaystyle 1\le K \le \frac N2
- The sum of N over all test cases is at most 10^6.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N K
Output
Print the answers to the test cases in order, separated by newlines.
Sample Input 1
4 3 1 6 3 9 2 483 101
Sample Output 1
6 0 982675409 845255482
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\times 1+30\times 0=6.