結果

問題 No.3062 Rotate and Maximize
ユーザー SPD_9X2
提出日時 2025-03-01 18:08:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 801 ms / 2,000 ms
コード長 2,359 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 160,904 KB
最終ジャッジ日時 2025-03-12 00:52:45
合計ジャッジ時間 22,078 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/12000

まず、最大値の個数を見ると何回shiftするか分かる。
元の位置はそのうちどれか

最大から2番目の位置の集合を考えて、最大とペアリングすることを考える
3番目と2番目の競合を考えると筋が悪いか？

最大値の初位置ごとに考える？
最大値の初期位置を決め撃つと、移動が一意に決まる


---

あ、最初のAは全部0なのか。
すると P[0] = N として良くて、最後の答にN倍すればOK
すると操作の内容もすべて決まる

A[i] = max(P[a],P[b],P[c]...P[k]) みたいなのが決まる。

xを置く位置を決めるとき、A[i]=x となる奴全てに影響できる位置である必要がある。
また、他のAを破壊してはダメ

---

A登場しない数の制約をまじめに書いた Ver

2
1 1
を修正

"""

import sys
from sys import stdin

mod = 998244353

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
for i in range(N):
    A[i] -= 1

if N-1 not in A:
    print (0)
    sys.exit()

ks = []
for i in range(N):
    if A[i] == N-1:
        ks.append(i)

# P[i]の取りうる最大値
M = [N-1] * N
for i in range(N):
    for k in ks:
        M[(i-k)%N] = min(M[(i-k)%N],A[i])

# 置ける場所の候補を列挙
adic = {}
for i in range(N):
    if A[i] not in adic:
        adic[A[i]] = 0
    adic[A[i]] += 1

C = [ {} for i in range(N) ]

for i in range(N):
    
    for k in ks:
        if (i-k)%N not in C[A[i]]:
            C[A[i]][(i-k)%N] = 0
        C[A[i]][(i-k)%N] += 1

D = [ [] for i in range(N) ]

for na in range(N):

    if len(C[na]) > 0:
        for pos in C[na]:
            flag = True
            if C[na][pos] != adic[na]:
                flag = False
            if M[pos] < na:
                flag = False
            if flag and pos != 0:
                D[na].append(pos)
    else:
        for pos in range(N):
            flag = True
            if M[pos] < na:
                flag = False
            if flag and pos != 0:
                D[na].append(pos)


D[-1] = [0]

E = [0] * N

ans = 1
for na in range(N-1,-1,-1):

    able = []
    for pos in D[na]:
        if E[pos] == 0:
            able.append(pos)
    ans *= len(able)
    ans %= mod
    if able:
        E[able[0]] = 1
    
print (ans * N % mod)
0