問題一覧 > 通常問題

No.1348 Split Tile

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 45
作問者 : PCTprobabilityPCTprobability / テスター : KoDKoD maguromaguro blackyukiblackyuki
3 ProblemId : 5750 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-16 17:42:34

問題文

正整数 $N$ が与えられます。$1$ から $N$ の番号がついたタイルを横 $1$ 列に番号 $1,2,...,N$ の順で並べます。タイル $A$ とタイル $B$ が連結しているとは、$|A-B|=1$ かつ、タイル $A$ とタイル $B$ が両方残っていることとします。 以下のような $N$ ターンからなるゲームをします。最初変数 $X$ は $0$ で初期化されています。

  • 残っているタイルを $1$ 個選んで取り除く。
  • 今残っているタイルの連結成分の個数を $X$ に足す。
あり得るゲームの進み方は $N!$ 通りありますが、その全てに対して最終的な $X$ の総和を $998244353$ で割った余りを求めてください。 ただし、$2$ 個のゲームの進み方が違うとは、ある正整数 $i$ が存在し、$i$ ターン目に取り除いたタイルの番号が $2$ 個のゲームで異なることとします。

入力

$N$

  • 入力は全て正整数である。
  • $1 \le N \le 10^6$

出力

あり得るゲームの進み方は $N!$ 通りありますが、その全てに対して最終的な $X$ の総和を $998244353$ で割った余りを求めてください。

サンプル

サンプル1
入力
3
出力
14

例えば、タイルを取り除く順番を $2,1,3$ としたら、$X$ は $2+1+0=3$ となります。

サンプル2
入力
2021
出力
421978734

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。