結果

問題 No.3119 A Little Cheat
ユーザー Kevgen
提出日時 2025-04-18 22:32:39
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 962 bytes
コンパイル時間 513 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 27,864 KB
最終ジャッジ日時 2025-04-18 22:32:47
合計ジャッジ時間 7,650 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    M = int(input[1])
    A = list(map(int, input[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:
        cnt = max(0, M - a)
        sum_s0 = (sum_s0 + cnt * powM[N-1]) % MOD
    
    sum_swap = 0
    for j in range(N-1):
        a = A[j]
        b = A[j+1]
        
        total = 0
        for B_j in range(1, M+1):
            for B_j1 in range(1, M+1):
                original = (B_j > a) + (B_j1 > b)
                swapped = (B_j1 > a) + (B_j > b)
                delta = swapped - original
                if delta > 0:
                    total += 1
        total %= MOD
        
        cnt = total * powM[N-2] % MOD
        sum_swap = (sum_swap + cnt) % MOD
    
    ans = (sum_s0 + sum_swap) % MOD
    print(ans)

if __name__ == '__main__':
    main()
0