結果

問題 No.2144 MM
コンテスト
ユーザー detteiuu
提出日時 2026-11-01 17:29:52
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 102 ms / 2,000 ms
+ 462µs
コード長 1,315 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 120 ms
コンパイル使用メモリ 64,356 KB
実行使用メモリ 89,600 KB
最終ジャッジ日時 2026-11-01 17:30:01
合計ジャッジ時間 5,782 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353

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

sum0 = 0
sum1 = 0
for i, a in enumerate(A):
    if i%2 == 0:
        sum0 += a
        sum0 %= M
    else:
        sum1 += a
        sum1 %= M
if sum0 != sum1:
    exit(print(-1))

C = [0, 1]
for n in range(2, N+1):
    C.append(C[-1]*(M-1)%MOD)
    if n%2 == 0:
        C[-1] -= 1
        C[-1] %= MOD
    else:
        C[-1] += 1
        C[-1] %= MOD

SUM = 0
ans = 1
a, b = (N+1)//2, N//2
for i in range(N):
    if i%2 == 0:
        a -= 1
    else:
        b -= 1
    if A[i] == 0: continue

    c, d = C[a], C[b]
    ans += A[i]*c%MOD*d%MOD*M%MOD
    ans %= MOD

    if a%2 == 0:
        ans += A[i]*d%MOD
        ans %= MOD
    else:
        ans -= A[i]*d%MOD
        ans %= MOD
    if b%2 == 0:
        ans += A[i]*c%MOD
        ans %= MOD
    else:
        ans -= A[i]*c%MOD
        ans %= MOD

    if i%2 == 0:
        l, r = SUM, SUM+A[i]-1
    else:
        l, r = SUM-A[i]+1, SUM
    l %= M
    r %= M
    if l > r: r += M
    m = (a-b)%M
    if l <= m <= r or l <= m+M <= r:
        if (a+b)%2 == 0:
            ans += 1
            ans %= MOD
        else:
            ans -= 1
            ans %= MOD

    if i%2 == 0:
        SUM += A[i]
        SUM %= M
    else:
        SUM -= A[i]
        SUM %= M

print(ans)
0