結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
|
提出日時 | 2025-04-19 13:11:36 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,397 bytes |
コンパイル時間 | 608 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 40,264 KB |
最終ジャッジ日時 | 2025-04-19 13:12:02 |
合計ジャッジ時間 | 22,603 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 49 |
ソースコード
MOD = 998244353 def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) M = int(data[1]) A = list(map(int, data[2:2+N])) powM = [1] * (N + 1) for i in range(1, N + 1): powM[i] = powM[i - 1] * M % MOD sum_s0 = 0 for a in A: count = max(0, M - a) sum_s0 = (sum_s0 + count * powM[N - 1]) % MOD total = sum_s0 for i in range(N - 1): a = A[i] a_next = A[i + 1] x_min = a + 1 x_max = M y_min = a_next + 1 y_max = M def count_xy(xl, xr, yl, yr): if xr < xl or yr < yl: return 0 return (xr - xl + 1) * (yr - yl + 1) case1 = count_xy(1, min(a, a_next), max(a, a_next) + 1, M) case2 = count_xy(max(a, a_next) + 1, M, 1, min(a, a_next)) case3 = count_xy(a_next + 1, a, a + 1, a_next) cross = 0 if a > a_next: cross = count_xy(a_next + 1, a, a_next + 1, a) same = 0 if a > a_next: same = count_xy(a_next + 1, a, a_next + 1, a) valid = (case1 + case2 + case3 - cross) % MOD other = powM[N - 2] if N >= 2 else 1 total = (total + valid * other) % MOD print(total % MOD) if __name__ == '__main__': main()