o642. F - 很多對對序列問題 - 高中生程式解題系統

內容

對對序列問題

我們說一個正整數序列為 k-對對序列 ( $k$ 為正整數) 如果它滿足以下條件：
這個序列長度為 $2 k$ ，且正整數 $1 \sim k$ 恰好在這個序列各出現 $2$ 次。

對於一個 k-對對序列 $S = (S_{1}, S_{2}, S_{3}, \dots, S_{2 k})$ ，因為上面的性質，我們想知道對於所有整數 $i$ 滿足 $1 \sim k$ ，考慮 $i$ 在 $S$ 中出現兩次的索引值的差(取正數)，請你算出這些差的加總。

如： $S = (2, 3, 1, 1, 3, 2)$ ，則：
當 $i = 1$ ：數字 $1$ 在 $S$ 內的索引值的差為 $1$
當 $i = 2$ ：數字 $2$ 在 $S$ 內的索引值的差為 $5$
當 $i = 3$ ：數字 $3$ 在 $S$ 內的索引值的差為 $3$
則答案為索引值差的加總，也就是 $1 + 5 + 3 = 9$ 。

Chung 看了上面問題覺得太簡單了，於是他就出了以下題目：

很多對對序列問題

給你一個正整數 $n$ ，請你求所有相異的 n-對對序列，它們對於對對序列問題的答案的總和模 $998244353$ 。

請解決很多對對序列問題。

輸入說明

輸入有一行一個正整數，代表 $n$ 。

$1 \leq n \leq 2 \times 10^{5}$

輸出說明

輸入一個整數代表答案。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

範例輸入 #3

範例輸出 #3

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (2%): 2.0s , <1K
公開測資點#1 (2%): 2.0s , <1K
公開測資點#2 (2%): 2.0s , <1K
公開測資點#3 (2%): 2.0s , <1K
公開測資點#4 (2%): 2.0s , <1K
公開測資點#5 (2%): 2.0s , <1K
公開測資點#6 (2%): 2.0s , <1K
公開測資點#7 (2%): 2.0s , <1K
公開測資點#8 (2%): 2.0s , <1K
公開測資點#9 (2%): 2.0s , <1K
公開測資點#10 (8%): 2.0s , <1K
公開測資點#11 (8%): 2.0s , <1K
公開測資點#12 (8%): 2.0s , <1K
公開測資點#13 (8%): 2.0s , <1K
公開測資點#14 (8%): 2.0s , <1K
公開測資點#15 (8%): 2.0s , <1K
公開測資點#16 (8%): 2.0s , <1K
公開測資點#17 (8%): 2.0s , <1K
公開測資點#18 (8%): 2.0s , <1K
公開測資點#19 (8%): 2.0s , <1K

提示：

範例 #1

符合的對對序列只有 $(1, 1)$ 一種，答案為 $1$ 。

範例 #2

符合的對對序列有 $6$ 個，我們分別討論他們對於對對序列問題的答案 (以下的索引值差順序先計算 $1$ 的再 $2$ ) 。

$S = (1, 1, 2, 2)$ ，答案為 $1 + 1 = 2$ 。

$S = (1, 2, 1, 2)$ ，答案為 $2 + 2 = 4$ 。

$S = (1, 2, 2, 1)$ ，答案為 $3 + 1 = 4$ 。

$S = (2, 1, 1, 2)$ ，答案為 $1 + 3 = 4$ 。

$S = (2, 1, 2, 1)$ ，答案為 $2 + 2 = 4$ 。

$S = (2, 2, 1, 1)$ ，答案為 $1 + 1 = 2$ 。

所以最後答案為 $2 + 4 + 4 + 4 + 4 + 2 = 20$ 。

Authored by r1cky

標籤:

出處:

第二屆Chi怪壓常比賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」