問題一覧 > 教育的問題

No.963 Kadomatsu Sequence Sequence (2)

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 18
作問者 : 37zigen / テスター : noshi91
お気に入りにしたユーザー ProblemId : 3747 / 自分の提出
問題文最終更新日: 2020-01-06 13:15:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
37zigenさん門松問題 (順位表) の他の問題:

Note

This problem is a version of No.336 Kadomatsu Sequence Sequence with stronger constraints.

Problem Statement

Consider all permutations of the positive integers from $1$ to $N$. How many of them are Kadomatsu sequence sequences? Find the answer modulo $1012924417=483\times 2^{21}+1$.

Here, when $3$ integers are arranged as $A$, $B$, $C$ from left to right, they form a Kadomatsu sequence if all the values are distinct and the $2$nd largest integer among $A$, $B$, $C$ is either $A$ or $C$.
Also, a sequence in which any $3$ consecutive integers form a Kadomatsu sequence is called a Kadomatsu sequence sequence.

Input

$N$

$3\leq N\leq 202020$

Output

Print a newline at the end.

Sample

Sample 1
Input
3
Output
4

For $N=3$, the permutations that are Kadomatsu sequence sequences are the following 4: $(1,3,2),(2,1,3),(2,3,1),(3,1,2)$.

Sample 2
Input
4
Output
10

Sample 3
Input
2016
Output
168501782

The original problem, No.336 Kadomatsu Sequence Sequence, was published on January 15, 2016.

Sample 4
Input
2020
Output
360793921

Happy New Year 2020!

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