問題一覧 > 通常問題

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=(A0,A1,…,AN−1)A=(A_0,A_1,\dots,A_{N-1}) と (1,2,…,N)(1,2,\dots,N) の順列 P=(P0,P1,…,PN−1)P=(P_0,P_1,\dots,P_{N-1}) を持っています。はじめ、 AA のすべての要素は 00 です。

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

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

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

入力

NN
A0 A1…AN−1A_0\ A_1\dots A_{N-1}

  • 入力はすべて整数である
  • 2≤N≤30002 \le N \le 3000
  • 1≤Ai≤N1 \le A_i \le N

出力

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

サンプル

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

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

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

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

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

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

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