結果

問題 No.3119 A Little Cheat
ユーザー keymoon
提出日時 2025-04-19 06:34:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 145 ms / 2,000 ms
コード長 1,060 bytes
コンパイル時間 585 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 107,776 KB
最終ジャッジ日時 2025-04-19 06:35:08
合計ジャッジ時間 8,575 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

n, m = map(int, input().split())
a = list(map(int, input().split()))

len_arr = [abs(a[i+1] - a[i]) for i in range(n-1)]
l = [min(a[i], a[i+1]) for i in range(n-1)]
r = [max(a[i], a[i+1]) for i in range(n-1)]
e = [0] * (n-2)
for i in range(n-2):
    left = max(l[i], l[i+1])
    right = min(r[i], r[i+1])
    e[i] = max(0, right - left)

t = m % MOD
s = len_arr[0] % MOD

for i in range(n-1):
    li = len_arr[i] % MOD
    if i == n-2:
        if a[i] <= a[i+1]:
            t = (t * (m - li) + s * li) % MOD
        else:
            t = (t * m - s * (m - li)) % MOD
    else:
        len2 = len_arr[i+1] % MOD
        ei = e[i] % MOD
        if a[i] <= a[i+1]:
            T_new = (t * (m - li) + s * li) % MOD
            S_new = (s * ei + t * (len2 - ei)) % MOD
        else:
            T_new = (t * m - s * (m - li)) % MOD
            S_new = (t * len2 - s * (len2 - ei)) % MOD
        t, s = T_new, S_new

s0 = sum((m - a) % MOD for a in a) * pow(m, n-1, MOD) % MOD
incr = (pow(m, n, MOD) - t) % MOD

ans = (s0 + incr) % MOD
print(ans)
0