結果

問題 No.3062 Rotate and Maximize
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2025-03-01 17:54:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,159 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 85,212 KB
最終ジャッジ日時 2025-03-12 00:52:23
合計ジャッジ時間 11,916 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 13
権限があれば一括ダウンロードができます

ソースコード

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を破壊してはダメ

---

よくわからないけど

2
2 2
で4になってしまうのでそれを修正



"""

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

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):
    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)

D[-1] = [0]
exist = set()
for na in range(N):
    for x in D[na]:
        exist.add(x)

ans = 1
free = N - len(exist)
for na in range(N-1,-1,-1):
    if na not in adic:
        ans *= free
        free -= 1
        ans %= mod
    else:
        ans *= len(D[na])
        free += len(D[na])-1
        ans %= mod

print (ans * N % mod)
0