問題一覧 > 通常問題

No.3062 Rotate and Maximize

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : 👑 tute7627 / テスター : 👑 SPD_9X2 👑 rin204
1 ProblemId : 12000 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-03-16 11:49:47

問題文

高橋君は数列 $A=(A_0,A_1,\dots,A_{N-1})$ と $(1,2,\dots,N)$ の順列 $P=(P_0,P_1,\dots,P_{N-1})$ を持っています。はじめ、 $A$ のすべての要素は $0$ です。

高橋君は以下の操作を $1$ 回以上行いました。

  • 整数 $k(0 \le k \le N-1)$ を選択し、 $i = 0,1,\dots,N-1$ について、 $A_i$ を $\max(A_i, P_{(i-k)\pmod N})$ で置き換える。

操作後の数列 $A$ が与えられます。順列 $P$ としてあり得るものの数を $998244353$ で割ったあまりを求めてください。

入力

$N$
$A_0\ A_1\dots A_{N-1}$

  • 入力はすべて整数である
  • $2 \le N \le 3000$
  • $1 \le A_i \le N$

出力

順列 $P$ としてあり得るものの数を $998244353$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3
2 3 3
出力
6

例えば $P = (2,3,1)$ である場合を考えます。 高橋君が以下の手順で操作を行った場合、数列 $A$ は入力と一致します。

  1. $k=0$ を選択する。$A=(\max(0,2), \max(0,3), \max(0,1)) = (2,3,1)$ となる。
  2. $k=1$ を選択する。$A=(\max(2,1), \max(3,2), \max(1,3)) = (2,3,3)$ となる。
$P$ が $(1,2,3)$ のどの順列であっても、$A=(2,3,3)$ となる可能性があります。

サンプル2
入力
3
1 3 3
出力
0

順列 $P$ としてあり得るものが存在しないこともあります。

サンプル3
入力
5
5 4 3 5 4
出力
20

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