No.1062 素敵なスコア
タグ : / 解いたユーザー数 12
作問者 :
Enjapma_kyopro
/ テスター :
okuraofvegetabl
問題文
長さが $N$ であるような、$($ $1$ , $2$ , ... , $N$ $)$ の順列に対して、以下のような $2$ 種類の操作を考えます。
操作 $i$ $($ $i = 1$ , $2$ $)$：
- $1$ . $K = A_i$ $($ $1 \le A_i \le N - 1$ $)$ と設定する。
- $2$ . 順列の中で、「$K$ よりも大きい要素で最も左のもの」と「$K$ 以下の要素で最も右のもの」を選ぶ。前者を $U$ 、後者を $V$ とする。
- $3$ . $U$ が $V$ よりも左にあるなら、$U$ と $V$ を交換して、手順 $2$ に戻る。そうでなければ、操作を終了する。
順列の「スコア」を、「順列に操作 $1$ を行った後の順列を $P$ 、操作 $2$ を行った後の順列を $Q$ としたとき、$P_i = Q_i$ となる $i$ の数 $($ $1 \le i \le N$ $)$ 」と定めます。
操作 $2$ は、操作 $1$ を行った後の順列ではなく、元の順列に対して行うことに注意してください。（5/22 22:18 追記）
（ここで、 $P_i$ は $P$ の $i$ 番目の要素を表します。）
長さ $N$ の考えられる全ての順列について、その「スコア」をすべて足し合わせた値はいくつになるでしょう？
ただし、答えは非常に大きくなることがあるので、 $998244353$ で割ったあまりを求めてください。
入力
$N\ A_1\ A_2$
- 入力はすべて整数
- $2 \le N \le 10^5$
- $1 \le A_1 \le N-1$
- $1 \le A_2 \le N-1$
出力
長さ $N$ の考えられる全ての順列について、その「スコア」をすべて足し合わせた値を $998244353$ で割ったあまりを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 1 2
出力
8
順列が $($ $1, 2, 3$ $)$ のとき、操作 $1$ を行うと $($ $1, 2, 3$ $)$ 、操作 $2$ を行うと $($ $1, 2, 3$ $)$ となり、「スコア」は $3$ です。
順列が $($ $1, 3, 2$ $)$ のとき、操作 $1$ を行うと $($ $1, 3, 2$ $)$ 、操作 $2$ を行うと $($ $1, 2, 3$ $)$ となり、「スコア」は $1$ です。
順列が $($ $2, 1, 3$ $)$ のとき、操作 $1$ を行うと $($ $1, 2, 3$ $)$ 、操作 $2$ を行うと $($ $2, 1, 3$ $)$ となり、「スコア」は $1$ です。
順列が $($ $2, 3, 1$ $)$ のとき、操作 $1$ を行うと $($ $1, 3, 2$ $)$ 、操作 $2$ を行うと $($ $2, 1, 3$ $)$ となり、「スコア」は $0$ です。
順列が $($ $3, 1, 2$ $)$ のとき、操作 $1$ を行うと $($ $1, 3, 2$ $)$ 、操作 $2$ を行うと $($ $2, 1, 3$ $)$ となり、「スコア」は $0$ です。
順列が $($ $3, 2, 1$ $)$ のとき、操作 $1$ を行うと $($ $1, 2, 3$ $)$ 、操作 $2$ を行うと $($ $1, 2, 3$ $)$ となり、「スコア」は $3$ です。
よって、これらを合計した $8$ を出力すれば良いです。
サンプル2
入力
5 3 3
出力
600
この場合、 $2$ つの操作は同じです。
つまり、どの順列に操作を行なってもすべての要素が一致するので、どの場合も「スコア」は $5$ です。
よって、求める値は $5 \times 5! = 600$ です。
サンプル3
入力
100 10 11
出力
271455420
$998244353$ で割ったあまりを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。