提出 #69533364

ソースコード 拡げる

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print(1)
    exit()
mod = 998244353
pre0, pre1 = -1, -1
if A[0] == -1:
    pre0 = N - 1
    pre1 = 1
elif A[0] == 2:
    pre0 = 0
    pre1 = 1
else:
    pre0 = 1
    pre1 = 0

for i in range(1, N - 1):
    dp0, dp1 = 0, 0
    if A[i] == -1:
        dp0 += pre0 + (N - 1) * pre1
        dp1 += pre1
    elif A[i] == i + 2:
        dp1 += pre1
    elif A[i] == i:
        dp0 += pre0 + pre1
    else:
        dp0 += (N - 2) * pre1
    dp0 %= mod
    dp1 %= mod
    pre0, pre1 = dp0, dp1

ans = 0
if A[-1] == -1:
    ans += pre1 * N + pre0
elif A[-1] == N - 1:
    ans += pre0 + pre1
else:
    ans += pre1

print(ans % mod)

提出情報

提出日時
問題 C - Tree Sequence
ユーザ rlangevin
言語 Python (PyPy 3.10-v7.3.12)
得点 600
コード長 728 Byte
結果 AC
実行時間 96 ms
メモリ 111748 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 3
AC × 34
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 02_min_00.txt, 02_min_01.txt, 02_min_02.txt, 02_min_03.txt, 02_min_04.txt, 02_min_05.txt, 02_min_06.txt, 02_min_07.txt, 02_min_08.txt, 02_min_09.txt, 02_min_10.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 67 ms 76432 KiB
00_sample_01.txt AC 62 ms 76596 KiB
00_sample_02.txt AC 63 ms 76588 KiB
01_random_00.txt AC 89 ms 104516 KiB
01_random_01.txt AC 82 ms 99064 KiB
01_random_02.txt AC 96 ms 111748 KiB
01_random_03.txt AC 93 ms 111240 KiB
01_random_04.txt AC 94 ms 111320 KiB
01_random_05.txt AC 87 ms 107284 KiB
01_random_06.txt AC 83 ms 101172 KiB
01_random_07.txt AC 89 ms 110992 KiB
01_random_08.txt AC 87 ms 111036 KiB
01_random_09.txt AC 93 ms 111364 KiB
01_random_10.txt AC 86 ms 110652 KiB
01_random_11.txt AC 85 ms 110300 KiB
01_random_12.txt AC 85 ms 110452 KiB
01_random_13.txt AC 83 ms 110336 KiB
01_random_14.txt AC 84 ms 110088 KiB
01_random_15.txt AC 83 ms 110092 KiB
01_random_16.txt AC 85 ms 110448 KiB
01_random_17.txt AC 86 ms 110240 KiB
01_random_18.txt AC 89 ms 110108 KiB
01_random_19.txt AC 84 ms 109980 KiB
02_min_00.txt AC 64 ms 76572 KiB
02_min_01.txt AC 62 ms 76692 KiB
02_min_02.txt AC 63 ms 76224 KiB
02_min_03.txt AC 65 ms 76664 KiB
02_min_04.txt AC 65 ms 76504 KiB
02_min_05.txt AC 69 ms 76620 KiB
02_min_06.txt AC 66 ms 76432 KiB
02_min_07.txt AC 67 ms 76428 KiB
02_min_08.txt AC 69 ms 76464 KiB
02_min_09.txt AC 68 ms 76572 KiB
02_min_10.txt AC 66 ms 76408 KiB