題目 2687:
藍(lán)橋杯2022年第十三屆省賽真題-全排列的價(jià)值
時(shí)間限制: 2s
內(nèi)存限制: 576MB 提交: 3930 解決: 776
題目描述
對于一個(gè)排列 A = (a1, a2, · · · , an)，定義價(jià)值 ci 為 a1 至 ai?1 中小于 ai 的數(shù)的個(gè)數(shù)，即 bi = |{aj | j < i, aj < ai}|。定義 A 的價(jià)值為
。
給定 n，求 1 至 n 的全排列中所有排列的價(jià)值之和。
輸入格式
輸入一行包含一個(gè)整數(shù) n 。
輸出格式
輸出一行包含一個(gè)整數(shù)表示答案，由于所有排列的價(jià)值之和可能很大，請輸出這個(gè)數(shù)除以 998244353 的余數(shù)。
樣例輸入
3
樣例輸出
9
提示
1 至 3 構(gòu)成的所有排列的價(jià)值如下:
(1, 2, 3) : 0 + 1 + 2 = 3 ；
(1, 3, 2) : 0 + 1 + 1 = 2 ；
(2, 1, 3) : 0 + 0 + 2 = 2 ；
(2, 3, 1) : 0 + 1 + 0 = 1 ；
(3, 1, 2) : 0 + 0 + 1 = 1 ；
(3, 2, 1) : 0 + 0 + 0 = 0 ；
故總和為 3 + 2 + 2 + 1 + 1 = 9。
對于 40% 的評測用例，n ≤ 20 ；
對于 70% 的評測用例，n ≤ 5000 ；
對于所有評測用例，2 ≤ n ≤ 106 。