結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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)