問題一覧 > 通常問題

No.3645 Count Shitoshitoto Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : kazuppa / テスター : Tamiji153 Unbakedbread
ProblemId : 13634 / Paken新入生コンday2 (順位表) / 自分の提出
問題文最終更新日: 2026-08-25 18:38:39
Paken新入生コンday2の他の問題:

問題文

以下の条件を満たす数列 $X$ をしとしとと数列と定義します。

  • $|X|=5$
  • $X_1=X_3$
  • $X_2=X_4=X_5$
  • $X_1\neq X_2$

正整数 $N$ が与えられます。全ての要素が $1$ 以上 $N$ 以下である整数列 $X$ の内、しとしとと数列であるものの個数を $998244353$ で割った余りを求めてください。

制約

  • $1\leq N\leq 10^6$
  • $N$ は整数

小課題

この問題にはサブタスクによる部分点が設定されています。

小課題名 配点 制約
小課題110 %$N\leq 2$
小課題230 %$N \le 30$
小課題360 %追加の制約はない

入力

$N$

出力

答えを一行に出力してください。

サンプル

サンプル1
入力
3
出力
6

例えば、$X=(3,2,3,2,2)$ や $X=(1,2,1,2,2)$ などは条件を満たします。

条件を満たす $X$ は全部で $6$ つあるので、$6$ を出力してください。

サンプル2
入力
1
出力
0

条件を満たす数列は存在しません。

サンプル3
入力
169231
出力
688120246

答えを $998244353$ で割った余りで出力することに注意してください。

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