No.1062 Nice Score
タグ : / 解いたユーザー数 14
作問者 :
Enjapma_kyopro
/ テスター :
okuraofvegetabl
Problem Statement
For a permutation of $($ $1$ , $2$ , ... , $N$ $)$ of length $N$, consider the following $2$ types of operations.
Operation $i$ $($ $i = 1$ , $2$ $)$:
- $1$ . Set $K = A_i$ $($ $1 \le A_i \le N - 1$ $)$.
- $2$ . In the permutation, choose "the leftmost element greater than $K$" and "the rightmost element less than or equal to $K$". Call the former $U$ and the latter $V$.
- $3$ . If $U$ is to the left of $V$, swap $U$ and $V$ and return to step $2$. Otherwise, end the operation.
Define the "score" of a permutation as follows: let $P$ be the permutation after applying operation $1$ to it and $Q$ be the permutation after applying operation $2$ to it; the "score" is the number of $i$ $($ $1 \le i \le N$ $)$ such that $P_i = Q_i$.
Note that operation $2$ is applied to the original permutation, not to the permutation after operation $1$ has been applied. (Added 5/22 22:18)
(Here, $P_i$ denotes the $i$-th element of $P$.)
What is the sum of the "scores" over all possible permutations of length $N$?
Since the answer can be very large, find it modulo $998244353$.
Input
$N\ A_1\ A_2$
- All inputs are integers
- $2 \le N \le 10^5$
- $1 \le A_1 \le N-1$
- $1 \le A_2 \le N-1$
Output
Output the sum of the "scores" over all possible permutations of length $N$, modulo $998244353$.
Print a newline at the end.
Sample
Sample 1
Input
3 1 2
Output
8
When the permutation is $($ $1, 2, 3$ $)$, operation $1$ gives $($ $1, 2, 3$ $)$ and operation $2$ gives $($ $1, 2, 3$ $)$, so the "score" is $3$.
When the permutation is $($ $1, 3, 2$ $)$, operation $1$ gives $($ $1, 3, 2$ $)$ and operation $2$ gives $($ $1, 2, 3$ $)$, so the "score" is $1$.
When the permutation is $($ $2, 1, 3$ $)$, operation $1$ gives $($ $1, 2, 3$ $)$ and operation $2$ gives $($ $2, 1, 3$ $)$, so the "score" is $1$.
When the permutation is $($ $2, 3, 1$ $)$, operation $1$ gives $($ $1, 3, 2$ $)$ and operation $2$ gives $($ $2, 1, 3$ $)$, so the "score" is $0$.
When the permutation is $($ $3, 1, 2$ $)$, operation $1$ gives $($ $1, 3, 2$ $)$ and operation $2$ gives $($ $2, 1, 3$ $)$, so the "score" is $0$.
When the permutation is $($ $3, 2, 1$ $)$, operation $1$ gives $($ $1, 2, 3$ $)$ and operation $2$ gives $($ $1, 2, 3$ $)$, so the "score" is $3$.
Therefore, you should output their sum, $8$.
Sample 2
Input
5 3 3
Output
600
In this case, the $2$ operations are the same.
That is, no matter which permutation the operations are applied to, all elements match, so the "score" is $5$ in every case.
Therefore, the desired value is $5 \times 5! = 600$.
Sample 3
Input
100 10 11
Output
271455420
Output the value modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。