問題一覧 > 教育的問題

No.963 門松列列（2）

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : 37zigen / テスター : noshi91
4 ProblemId : 3747 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-01-06 13:15:43

Note

この問題はNo.336 門松列列の制約強化版です。

問題文

1からNまでの正の整数の並べ替えを順列ですべて行うとき、門松列列になっているものはいくつあるか？1012924417=483×221+1で割った余りを答えよ。

ただし、門松列とは3つの整数が左からA、B、Cと並んでいる時に、全ての値が異なりA、B、Cのうち2番目に大きな整数がAかCである場合をいう。
また、どの連続した3つの整数を取り出しても門松列になっている数列を門松列列と呼ぶ。

入力

N

3≤N≤202020

出力

最後に改行してください。

サンプル

サンプル1
入力
3
出力
4

N=3のとき門松列列となる順列は、(1,3,2),(2,1,3),(2,3,1),(3,1,2)の4つである。

サンプル2
入力
4
出力
10

サンプル3
入力
2016
出力
168501782

原題No.336 門松列列は2016年1月15日に出題された。

サンプル4
入力
2020
出力
360793921

2020年明けましておめでとうございます。

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