305803: CF1091D. New Year and the Permutation Concatenation

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

New Year and the Permutation Concatenation

题意翻译

设$n$为一个整数。把所有$1$到$n$的排列按字典序连接起来,使之变成一个更长的序列$p$。比如,$n=3$时,序列$p$为$[1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1]$。显然,$p$的长度为$n$·$n!$。 把任意满足$1\leq i \leq j \leq n$·$n!$ 的序列 $(p_i,p_{i+1},...,p_{j-1},p_j)$称为$p$的子列,其长度定义为$j-i+1$,其和定义为所有元素的总和,即 $\sum_{k=i}^j p_k$。 给定整数$n$,求出有多少个长度为$n$、和为$n(n+1)/2$的$p$的子列,答案对素数$998244353$取模。

题目描述

Let $ n $ be an integer. Consider all permutations on integers $ 1 $ to $ n $ in lexicographic order, and concatenate them into one big sequence $ p $ . For example, if $ n = 3 $ , then $ p = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1] $ . The length of this sequence will be $ n \cdot n! $ . Let $ 1 \leq i \leq j \leq n \cdot n! $ be a pair of indices. We call the sequence $ (p_i, p_{i+1}, \dots, p_{j-1}, p_j) $ a subarray of $ p $ . Its length is defined as the number of its elements, i.e., $ j - i + 1 $ . Its sum is the sum of all its elements, i.e., $ \sum_{k=i}^j p_k $ . You are given $ n $ . Find the number of subarrays of $ p $ of length $ n $ having sum $ \frac{n(n+1)}{2} $ . Since this number may be large, output it modulo $ 998244353 $ (a prime number).

输入输出格式

输入格式


The only line contains one integer $ n $ ( $ 1 \leq n \leq 10^6 $ ), as described in the problem statement.

输出格式


Output a single integer — the number of subarrays of length $ n $ having sum $ \frac{n(n+1)}{2} $ , modulo $ 998244353 $ .

输入输出样例

输入样例 #1

3

输出样例 #1

9

输入样例 #2

4

输出样例 #2

56

输入样例 #3

10

输出样例 #3

30052700

说明

In the first sample, there are $ 16 $ subarrays of length $ 3 $ . In order of appearance, they are: $ [1, 2, 3] $ , $ [2, 3, 1] $ , $ [3, 1, 3] $ , $ [1, 3, 2] $ , $ [3, 2, 2] $ , $ [2, 2, 1] $ , $ [2, 1, 3] $ , $ [1, 3, 2] $ , $ [3, 2, 3] $ , $ [2, 3, 1] $ , $ [3, 1, 3] $ , $ [1, 3, 1] $ , $ [3, 1, 2] $ , $ [1, 2, 3] $ , $ [2, 3, 2] $ , $ [3, 2, 1] $ . Their sums are $ 6 $ , $ 6 $ , $ 7 $ , $ 6 $ , $ 7 $ , $ 5 $ , $ 6 $ , $ 6 $ , $ 8 $ , $ 6 $ , $ 7 $ , $ 5 $ , $ 6 $ , $ 6 $ , $ 7 $ , $ 6 $ . As $ \frac{n(n+1)}{2} = 6 $ , the answer is $ 9 $ .

Input

题意翻译

设$n$为一个整数。把所有$1$到$n$的排列按字典序连接起来,使之变成一个更长的序列$p$。比如,$n=3$时,序列$p$为$[1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1]$。显然,$p$的长度为$n$·$n!$。 把任意满足$1\leq i \leq j \leq n$·$n!$ 的序列 $(p_i,p_{i+1},...,p_{j-1},p_j)$称为$p$的子列,其长度定义为$j-i+1$,其和定义为所有元素的总和,即 $\sum_{k=i}^j p_k$。 给定整数$n$,求出有多少个长度为$n$、和为$n(n+1)/2$的$p$的子列,答案对素数$998244353$取模。

加入题单

上一题 下一题 算法标签: