結果

問題 No.3119 A Little Cheat
ユーザー Kevgen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0