codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1091D.md (1787B)


      1 Source: https://codeforces.com/problemset/problem/1091/D
      2 
      3 D. New Year and the Permutation Concatenation
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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!$.
     22 
     23 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$.
     24 
     25 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).
     26 
     27 Input
     28 
     29 The only line contains one integer $n$ ($1 \leq n \leq 10^6$), as described in the problem statement.
     30 
     31 Output
     32 
     33 Output a single integer — the number of subarrays of length $n$ having sum $\frac{n(n+1)}{2}$, modulo $998244353$.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 3
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 9
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 4
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 56
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 10
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 30052700
     71 ```
     72 
     73 Note
     74 
     75 In the first sample, there are $16$ subarrays of length $3$. In order of appearance, they are:
     76 
     77 $[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]$.
     78 
     79 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$.