Problem:


Score : 900 points

Problem Statement

You are given a sequence of N integers: A_1,A_2,...,A_N.

Find the number of permutations p_1,p_2,...,p_N of 1,2,...,N that can be changed to A_1,A_2,...,A_N by performing the following operation some number of times (possibly zero), modulo 998244353:

For each 1\leq i\leq N, let q_i=min(p_{i-1},p_{i}), where p_0=p_N. Replace the sequence p with the sequence q.

Constraints

1 \leq N \leq 3 × 10^5

1 \leq A_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the number of the sequences that satisfy the condition, modulo 998244353.

Sample Input 1

3
1
2
1

Sample Output 1

2

(2,3,1) and (3,2,1) satisfy the condition.

Sample Input 2

5
3
1
4
1
5

Sample Output 2

0

Sample Input 3

8
4
4
4
1
1
1
2
2

Sample Output 3

24

Sample Input 4

6
1
1
6
2
2
2

Sample Output 4

0



Sample input:
3
1
2
1


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N,*A = map(int,read().split())

T = A.count(1)
if T == 0:
    print(0)
    exit()
if T == 1:
    answer = 1 if len(set(A)) == N else 0
    print(answer)
    exit()
if T == N:
    answer = 1
    for n in range(1,N+1):
        answer *= n
        answer %= MOD
    print(answer)
    exit()

n = A.index(1)
while A[n-1] == 1:
    n -= 1
A = A[n:] + A[:n]

assert len(A) == N and A[0] == 1 and A[-1] != 1
print(0)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

M = 998244353
N = int(input())
A = np.empty(N, dtype=np.int64)
for i in range(N):
    A[i] = int(input()) - 1
    # A[i]: 0,1,...,(N-1)

s=0
if A[0]==A[N-1]:
    while (s <= N-1) and (A[s]==A[0]):
        s = s+1
if s == N:
    if A[0] == 0:
        result = 1
        for i in range(1,N):
            result = (result*i) % M
        print(result)
    else:
        print(0)

    sys.exit()

lengths = np.zeros(N, dtype=np.int64)
heads = np.zeros(N, dtype=np.int64)
tails = np.zeros(N, dtype=np.int64)

if s > 0:
    tail = A[0]
else:
    tail = A[N-1]

l = 1
for i in range(s,N):
    if (i < N-1) and (A[i+1] == A[i]):
        l = l+1
    else:
        if i < N-1:
            if lengths[A[i+1]] > 0:
                print(0)
                sys.exit()
            else:
                heads[A[i]] = A[i+1]
        else:
            heads[A[i]] = A[0]

        lengths[A[i]] = l
        l=1
        tails[A[i]] = tail
        tail = A[i]
if s > 0:
    heads[A[0]] = A[s]
    lengths[A[0]] = lengths[A[0]] + s

k = lengths[0]
if k == 0:
    print(0)
    sys.exit()

result = 1
killed = 0
for i in range(1,N):
    if lengths[i] == 0:
        result = (result * killed) % M
        killed = killed - 1
    elif lengths[i] > k:
        print(0)
        exit()
    elif heads[i] > i and tails[i] > i:
        if lengths[i] != k:
            print(0)
            exit()
    elif heads[i] < i and tails[i] < i:
        result = (result * (k-lengths[i]+1)) % M
        killed = killed + (lengths[i]+k-2)
    else:
        # head < i and tail > i
        # head > i and tail < i
        killed = killed + (lengths[i]-1)

print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

M = 998244353
N = int(input())
A = np.empty(N, dtype=np.int64)
for i in range(N):
    A[i] = int(input()) - 1
    # A[i]: 0,1,...,(N-1)

s=0
if A[0]==A[N-1]:
    while (s <= N-1) and (A[s]==A[0]):
        s = s+1
if s == N:
    if A[0] == 0:
        result = 1
        for i in range(1,N+1):
            result = (result*i) % M
        print(result)
    else:
        print(0)

    sys.exit()

lengths = np.zeros(N, dtype=np.int64)
heads = np.zeros(N, dtype=np.int64)
tails = np.zeros(N, dtype=np.int64)

if s > 0:
    tail = A[0]
else:
    tail = A[N-1]

l = 1
for i in range(s,N):
    if (i < N-1) and (A[i+1] == A[i]):
        l = l+1
    else:
        if i < N-1:
            if lengths[A[i+1]] > 0:
                print(0)
                sys.exit()
            else:
                heads[A[i]] = A[i+1]
        else:
            heads[A[i]] = A[0]

        lengths[A[i]] = l
        l=1
        tails[A[i]] = tail
        tail = A[i]
if s > 0:
    heads[A[0]] = A[s]
    lengths[A[0]] = lengths[A[0]] + s

k = lengths[0]
if k == 0:
    print(0)
    sys.exit()

result = 1
killed = 0
for i in range(1,N):
    if lengths[i] == 0:
        result = (result * killed) % M
        killed = killed - 1
    elif lengths[i] > k:
        print(0)
        exit()
    elif heads[i] > i and tails[i] > i:
        if lengths[i] != k:
            print(0)
            exit()
    elif heads[i] < i and tails[i] < i:
        result = (result * (k-lengths[i]+1)) % M
        killed = killed + (lengths[i]+k-2)
    else:
        # head < i and tail > i
        # head > i and tail < i
        killed = killed + (lengths[i]-1)

print(result)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from operator import itemgetter

MOD = 998244353

N,*A = map(int,read().split())

T = A.count(1)
if T == 0:
    print(0)
    exit()
if T == 1:
    answer = 1 if len(set(A)) == N else 0
    print(answer)
    exit()
if T == N:
    answer = 1
    for n in range(1,N+1):
        answer *= n
        answer %= MOD
    print(answer)
    exit()

n = A.index(1)
while A[n-1] == 1:
    n -= 1
A = A[n:] + A[:n]

# assert len(A) == N and A[0] == 1 and A[-1] != 1

L = [0] * (N+1)
R = [-1] * (N+1)
ctr = [0] * (N+1)
nums = []
prev = 0
for i,x in enumerate(A):
    ctr[x] += 1
    R[x] = i
    if prev != x:
        nums.append(x)
        L[x] = i
        prev = x

if any(y - x + 1 != z for x,y,z in zip(L,R,ctr)):
    print(0)
    exit()
if any(x > T for x in ctr[2:]):
    print(0)
    exit()

free = [0] * (N+1) # ある数値を書き込んだ時点で、死亡確定になってるマス数
answer = 1
for x,y,z in zip(nums,nums[1:],nums[2:]+[1]):
    if x > y < z:
        if ctr[y] != T:
            answer = 0
            break
    elif x < y < z:
        free[y] += ctr[y] - 1
    elif x > y > z:
        free[y] += ctr[y] - 1
    else:
        # x < y > z
        answer *= (T + 1 - ctr[y])
        answer %= MOD
        free[y] += ctr[y] + T - 2

f = 0
for n in range(1,N+1):
    if ctr[n] >= 1:
        f += free[n]
        continue
    answer *= f
    answer %= MOD
    f -= 1

print(answer)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from operator import itemgetter

MOD = 998244353

N,*A = map(int,read().split())

T = A.count(1)
if T == 0:
    print(0)
    exit()
if T == 1:
    answer = 1 if len(set(A)) == N else 0
    print(answer)
    exit()
if T == N:
    answer = 1
    for n in range(1,N+1):
        answer *= n
        answer %= MOD
    print(answer)
    exit()

n = A.index(1)
while A[n-1] == 1:
    n -= 1
A = A[n:] + A[:n]

# assert len(A) == N and A[0] == 1 and A[-1] != 1

L = [0] * (N+1)
R = [-1] * (N+1)
ctr = [0] * (N+1)
nums = []
prev = 0
for i,x in enumerate(A):
    ctr[x] += 1
    R[x] = i
    if prev != x:
        nums.append(x)
        L[x] = i
        prev = x

if any(y - x + 1 != z for x,y,z in zip(L,R,ctr)):
    print(0)
    exit()
if any(x > T for x in ctr[2:]):
    print(0)
    exit()

raise Exception

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N,*A = map(int,read().split())

T = A.count(1)
if T == 0:
    print(0)
    exit()
if T == 1:
    answer = 1 if len(set(A)) == N else 0
    print(answer)
    exit()
if T == N:
    answer = 1
    for n in range(1,N+1):
        answer *= n
        answer %= MOD
    print(answer)
    exit()

n = A.index(1)
while A[n-1] == 1:
    n -= 1
A = A[n:] + A[:n]

# assert len(A) == N and A[0] == 1 and A[-1] != 1

L = [0] * (N+1)
R = [-1] * (N+1)
ctr = [0] * (N+1)
prev = 0
for i,x in enumerate(A):
    ctr[x] += 1
    R[x] = i
    if prev != x:
        L[x] = i
        prev = x

if any(y - x + 1 != z for x,y,z in zip(L,R,ctr)):
    print(0)
    exit()

raise Exception

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N,*A = map(int,read().split())

T = A.count(1)
if T == 1:
    answer = 1 if len(set(A)) == N else 0
    print(answer)
    exit()
if T == N:
    answer = 1
    for n in range(1,N+1):
        answer *= n
        answer %= MOD
    print(answer)
    exit()

n = A.index(1)
while A[n-1] == 1:
    n -= 1
A = A[n:] + A[:n]

assert len(A) == N and A[0] == 1 and A[-1] != 1
print(0)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N,*A = map(int,read().split())

T = A.count(1)
if T == 1:
    answer = 1 if len(set(A)) == N else 0
    print(answer)
    exit()
if T == N:
    answer = 1
    for n in range(1,N+1):
        answer *= n
        answer %= MOD
    print(answer)
    exit()

raise

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

M = 998244353
N = int(input())
A = np.empty(N, dtype=np.int64)
for i in range(N):
    A[i] = int(input())

if A[0]==A[N-1]==1:
    nps = np.where(A!=1)[0]
    if nps.max() - nps.min() + 1 != len(nps):
        print(0)
        sys.exit()
    else:
        k = N - len(nps)
else:
    ps = np.where(A==1)[0]
    if ps.max() - ps.min() + 1 != len(ps):
        print(0)
        sys.exit()
    else:
        k = len(ps)

if k == 0:
    print(0)
    sys.exit()

result = 1
killed = 0
for i in range(2,N+1):
    if A[0]==A[N-1]==i:
        nps = np.where(A!=i)[0]
        a = nps.min()
        b = nps.max()
        if b - a + 1 != len(nps):
            print(0)
            sys.exit()
        else:
            length = N - len(nps)
            head = A[a]
            tail = A[b]
    else:
        ps = np.where(A==i)[0]
        length = len(ps)
        if length > 0:
            a = ps.min()
            b = ps.max()
            if b - a + 1 != len(ps):
                print(0)
                sys.exit()
            else:
                if a == 0:
                    tail = A[N-1]
                else:
                    tail = A[a-1]
                if b == N-1:
                    head = A[0]
                else:
                    head = A[b+1]

    if length == 0:
        result = (result * killed) % M
        killed = killed - 1
    elif length > k:
        print(0)
        exit()
    elif head > i and tail > i:
        if length != k:
            print(0)
            exit()
    elif head < i and tail < i:
        result = (result * (k-length+1)) % M
        killed = killed + (length+k-2)
    else:
        # head < i and tail > i
        # head > i and tail < i
        killed = killed + (length-1)

print(result)