結果

問題 No.3119 A Little Cheat
ユーザー SPD_9X2
提出日時 2025-04-20 03:40:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 193 ms / 2,000 ms
コード長 4,130 bytes
コンパイル時間 731 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 104,028 KB
最終ジャッジ日時 2025-04-20 03:40:19
合計ジャッジ時間 8,969 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 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 -> 違反できる


1,1 : Y 
1,2 : 違反
1,3 : N
1,4 : N
2,1 : Y
2,2 : Y
2,3 : N
2,4 : N
3,1 : Y
3,2 : Y
3,3 : N
3,4 : N
4,1 : Y
4,2 : Y
4,3 : N
4,4 : N

8*4 = 32

1 2 3
  2 3
  1 

7 * 1

---

既に片側満たしているのが、両側になることがある？

A[i] < B[i+1] < A[i+1] < B[i]
A[i+1] < B[i] < A[i] < B[i+1]
あるなー


B[i] <= A[i] < B[i+1] <= A[i+1]
        A[i] < B[i+1] <= A[i+1] < B[i]

B[i+1] <= A[i+1] < B[i] <= A[i]
          A[i+1] < B[i] <= A[i] < B[i+1]

の4つの条件をまとめたい

"""

# LR1の範囲からLR2の区間を取り除いた長さ

def sub( L1,R1,L2,R2 ):

    if L1 > R1:
        assert False
    if L2 > R2:
        assert False
    
    if L2 <= L1 and R1 <= R2:
        return 0
    elif R2 < L1 or R1 < L2:
        return R1-L1+1
    else:
        return max(0,L2-L1) + max(0,R1-R2)

#LR1とLR2の区間の重複長さを返す

def mul( L1,R1,L2,R2 ):

    if L1 > R1:
        return 0
    if L2 > R2:
        return 0
    
    R = min(R1,R2)
    L = max(L1,L2)
    return max(0, R-L+1)

mod = 998244353

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

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

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

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

# print (dp)

for i in range(1,N):

    ndp = [0,0]

    # 違反の危険性がない場合、後ろだけを見て決められる

    D = abs(A[i+1]-A[i])
    if A[i] < A[i+1]:
        ndp[0] += D * dp[0]
        ndp[1] += (M-D) * dp[0]
    elif A[i+1] < A[i]:
        ndp[0] += (M-D) * dp[0]
        ndp[1] += D * dp[0]
    else:
        ndp[0] += M * dp[0]

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

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

        else: # A[i] == A[i+1]
            ndp[0] += sub(1,M,XL,XR) * dp[1]

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

        # B[i+1] <= A[i+1] < B[i] <= A[i] < B[i+1]
        # 逆に、許可の区間が XL~XR
        XL = A[i] + 1
        XR = A[i-1]

        if A[i] < A[i+1]:
            ndp[0] += mul(A[i]+1,A[i+1],XL,XR) * dp[1]
            ndp[1] += (
                mul(1,A[i],XL,XR) +
                mul(A[i+1]+1,M,XL,XR) ) * dp[1]
        elif A[i] > A[i+1]:
            ndp[1] += mul(A[i+1]+1,A[i],XL,XR) * dp[1]
            ndp[0] += (
                mul(1,A[i+1],XL,XR) +
                mul(A[i]+1,M,XL,XR) ) * dp[1]
        else:
            ndp[0] += mul(1,M,XL,XR) * 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