結果

問題 No.3119 A Little Cheat
ユーザー SPD_9X2
提出日時 2025-04-19 18:56:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,642 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 82,968 KB
実行使用メモリ 107,568 KB
最終ジャッジ日時 2025-04-19 18:56:14
合計ジャッジ時間 13,083 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/no/3119

2増える or 1増える or 変化なし
増えるものはいくつあるか？を数え上げればいい？

2増える場合は
A[i] < B[i+1]
A[i+1] < B[i]
A[i] >= B[i]
A[i+1] >= B[i+1]
これは存在しない

1増える場合
B[i] <= A[i] < B[i+1] <= A[i+1]
OR
B[i+1] <= A[i+1] < B[i] <= A[i]

なら成立

dp[i][既にあるか?][ B[i-1]<A[i-1]か？ ]
でdpすれば行けそう?

2つ同時に決めないとダメかなぁ

いや、増えないものを数え上げたほうがいい
dp[i][次で違反の可能性があるか？]
で良いのかなぁ

1 2
1 2,3,4 -> 違反できる


"""

mod = 998244353

N,M = map(int,input().split())
A = list(map(int,input().split()))

# dp[0] = 次違反する可能性がない
# dp[1] = 次違反する可能性がある

i = 0
if A[i] < A[i+1]:
    dp = [ M-A[i] , A[i] ]
elif A[i+1] < A[i]:
    dp = [ M-(A[i]-A[i+1]) , A[i]-A[i+1] ]
else:
    dp = [ M , 0 ]

print (dp)

# 同じ値を置くことで、番兵とする
A.append(A[-1])

for i in range(1,N):

    ndp = [0,0]

    # 違反の危険性がない場合、後ろだけを見て決められる
    if A[i] < A[i+1]:
        ndp[0] += (M-A[i]) * dp[0]
        ndp[1] += A[i] * dp[0]
        
    elif A[i+1] < A[i]:
        ndp[0] += (M-(A[i]-A[i+1])) * dp[0]
        ndp[1] += (A[i]-A[i+1]) * dp[0]
    else:
        ndp[0] += M * dp[0]

    # 違反の可能性がある場合は、大小関係で場合分け...
    if A[i-1] < A[i]:
        # A[i-1] < B[i] <= A[i] は設置禁止

        if A[i] < A[i+1]:
            # A[i]より大きい位置に配置する場合
            ndp[0] += ( M-A[i] ) * dp[1]
            # A[i-1]以下に設置する場合
            ndp[1] += ( A[i-1] ) * dp[1]
            
        elif A[i] > A[i+1]:
            p1 = max(0, A[i-1]-A[i+1])
            ndp[0] += ( M - (A[i]-A[i-1]) - p1 ) * dp[1]
            ndp[1] += p1 * dp[1]

        else: # A[i] == A[i+1]
            ndp[0] += ( M-(A[i]-A[i-1]) ) * dp[1]

    elif A[i-1] > A[i]:

        # B[i] <= A[i] が禁止
        # A[i] < B[i] となるようにB[i]を決めることとなり
        # この時点ですでにB[i+1]をどう配置しても不等式条件を満たすことは無い
        ndp[0] += (M - A[i]) * dp[1]
        
    else:
        # dp[1] = 0のはずなので
        pass
            
    dp = [x % mod for x in ndp]

    print (dp)


# 動かさない場合のスコア
X = pow(M,N-1,mod)
base = 0
for i in range(N):
    base += (M-A[i]) * X
    base %= mod

print (base , pow(M,N,mod) ,- dp[0])
ans = (base + pow(M,N,mod) - dp[0]) % mod
print (ans)
0