結果
問題 | No.2144 MM |
ユーザー |
![]() |
提出日時 | 2022-12-02 22:41:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 1,496 bytes |
コンパイル時間 | 2,104 ms |
コンパイル使用メモリ | 193,040 KB |
最終ジャッジ日時 | 2025-02-09 04:05:32 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define INF 1234567890 #define ll long long #define MOD 998244353 int N, M; int A[200201]; ll dp[200201]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin >> N >> M; // dp[0][0] = 1; // for(int i=1; i<=N; i++) // { // for(int j=0; j<M; j++) // { // for(int k=0; k<=M-2; k++) // dp[i][j] += dp[i-1][(-(j-k)%M+M)%M]; // cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << "\n"; // } // cout << "\n"; // } ll sum = 0; for(int i=1; i<=N; i++) { cin >> A[i]; if (i%2 == 1) sum += A[i]; else sum -= A[i]; } sum %= M; sum += M; sum %= M; if (sum) { cout << "-1\n"; return 0; } dp[0] = 0; for(int i=1; i<=N; i++) { if (i%2 == 0) dp[i] = (dp[i-1] * (M-1) - 1) % MOD; else dp[i] = (dp[i-1] * (M-1) + 1) % MOD; } sum = 0; ll res = 0; for(int i=1; i<=N-1; i++) { // 2 3 4 case // 0 x x // 1 x x // 2 0 x // 2 1 x // 2 2 x // 2 3 0 // 2 3 1 // 2 3 2 // 2 3 3 // 2 3 4 // sum -> -sum+k sum = -sum, sum %= M, sum += M, sum %= M; if (A[i] > 0) { res += dp[N-i] * A[i], res %= MOD; // [sum, sum+A[i]-1] ll L = sum, R = sum+A[i]-1; if ((N-i)%2 == 1 && L <= M-1 && M-1 <= R) res--; if ((N-i)%2 == 0 && ((L <= 0 && 0 <= R) || (L <= M && M <= R))) res++; // } sum += A[i], sum %= M; } // i = N case assert(sum <= A[N]); res++; res %= MOD; res += MOD; res %= MOD; cout << res << "\n"; return 0; }