Submission #42987954

Source Code Expand

MOD_BY = 998244353

N,M = map(int, input().split())

same = [0 for _ in range(N+1)]  # i番目まで見たときに1番目と同じ値を取る通り
vary = [0 for _ in range(N+1)]  # i番目まで見たときに1番目と異なる値を取る通り

same[1] = M
vary[1] = 0

for i in range(2,N+1):
    same[i] = vary[i-1]                             # i番目自体は1番目と同じ値を取るので1通り。最初と同じ値は続かないのでvaryを引き継ぐ
    vary[i] = same[i-1] * (M-1) + vary[i-1] * (M-2) # 左隣が1番目と同じ値の場合は、その値だけ除外。異なる値の場合は、1番目の値と左隣の値が除外。
    same[i] %= MOD_BY
    vary[i] %= MOD_BY

print(vary[N])

Submission Info

Submission Time
Task E - Distinct Adjacent
User tonomotohide
Language PyPy3 (7.3.0)
Score 475
Code Size 736 Byte
Status AC
Exec Time 173 ms
Memory 166832 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 475 / 475
Status
AC × 3
AC × 24
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 126 ms 131156 KiB
hand_02.txt AC 102 ms 110952 KiB
random_01.txt AC 170 ms 166480 KiB
random_02.txt AC 101 ms 116744 KiB
random_03.txt AC 84 ms 93808 KiB
random_04.txt AC 95 ms 111340 KiB
random_05.txt AC 171 ms 166312 KiB
random_06.txt AC 160 ms 165176 KiB
random_07.txt AC 91 ms 101540 KiB
random_08.txt AC 67 ms 72388 KiB
random_09.txt AC 170 ms 166260 KiB
random_10.txt AC 77 ms 81036 KiB
random_11.txt AC 97 ms 111712 KiB
random_12.txt AC 67 ms 68480 KiB
random_13.txt AC 173 ms 166140 KiB
random_14.txt AC 149 ms 166832 KiB
random_15.txt AC 160 ms 165096 KiB
random_16.txt AC 153 ms 166476 KiB
random_17.txt AC 53 ms 61776 KiB
random_18.txt AC 169 ms 166484 KiB
random_19.txt AC 56 ms 61568 KiB
sample_01.txt AC 56 ms 61720 KiB
sample_02.txt AC 54 ms 61728 KiB
sample_03.txt AC 171 ms 166464 KiB