問題一覧 > 通常問題

No.1062 素敵なスコア

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 10
作問者 : Enjapma_kyoproEnjapma_kyopro / テスター : okuraofvegetablokuraofvegetabl
4 ProblemId : 4315 / 出題時の順位表
問題文最終更新日: 2020-05-24 12:24:59

問題文

長さが $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もしくは右上の雲マークをクリックしてアカウントを作成してください。