問題一覧 > 通常問題

No.3062 Rotate and Maximize

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 26
作問者 : 👑 tute7627 / テスター : SPD_9X2 👑 rin204
お気に入りにしたユーザー ProblemId : 12000 / 自分の提出
問題文最終更新日: 2025-03-16 11:49:47
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
yukicoder contest 460 (順位表) の他の問題:

Problem Statement

Takahashi has a sequence $A=(A_0,A_1,\dots,A_{N-1})$ and a permutation $P=(P_0,P_1,\dots,P_{N-1})$ of $(1,2,\dots,N)$. Initially, all elements of $A$ are $0$.

Takahashi performed the following operation $1$ or more times.

  • Choose an integer $k(0 \le k \le N-1)$, and for each $i = 0,1,\dots,N-1$, replace $A_i$ with $\max(A_i, P_{(i-k)\pmod N})$.

You are given the sequence $A$ after the operations. Find the number of possible permutations $P$, modulo $998244353$.

Input

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

  • All input values are integers.
  • $2 \le N \le 3000$
  • $1 \le A_i \le N$

Output

Output the number of possible permutations $P$, modulo $998244353$. Print a newline at the end.

Sample

Sample 1
Input
3
2 3 3
Output
6

For example, consider the case $P = (2,3,1)$. If Takahashi performs the operations in the following steps, the sequence $A$ matches the input.

  1. Choose $k=0$. This gives $A=(\max(0,2), \max(0,3), \max(0,1)) = (2,3,1)$.
  2. Choose $k=1$. This gives $A=(\max(2,1), \max(3,2), \max(1,3)) = (2,3,3)$.
For any permutation $P$ of $(1,2,3)$, it is possible that $A=(2,3,3)$.

Sample 2
Input
3
1 3 3
Output
0

There may be no possible permutation $P$.

Sample 3
Input
5
5 4 3 5 4
Output
20

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