题目描述
(1,2,…,2N) の順列 P=(P1,P2,…,P2N) に対し、スコアを以下で定義します。
P を順序を保ったまま二つの長さ N の(連続するとは限らない)部分列 $ A\ =\ (A_1,A_2,\ldots,A_N),B\ =\ (B_1,B_2,\ldots,B_N) $ に分割する。分割を行ったときに得られる i=1∑NAi Bi の最大値をスコアとする。
(1,2,…,2N) の順列全てについてスコアを計算し、それらの最大値を M とします。 (1,2,…,2N) の順列のうち、スコアが M であるものの個数を 998244353 で割ったあまりを求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
N
输出格式
答えを出力せよ。
题目大意
给定 n
,输 2⋅n
的所有排列中,将其分成两个大小为 n
的子序列 A , B
,使得 Hn=∑i=1n Ai⋅ Bi 为最大值的方案数。
2
16
10000
391163238
提示
制約
- 1 ≤ N ≤ 2× 105
- 入力は全て整数
Sample Explanation 1
考えられる順列 24 通りの中で、スコアの最大値 M は 14 です。スコアが 14 となる順列は 16 通りあります。 例えば、順列 (1,2,3,4) は A=(1,3), B=(2,4) と分割することで、∑ i=1NAi Bi = 14 となります。
Sample Explanation 2
998244353 で割ったあまりを答えてください。