結果
問題 |
No.1887 K Consecutive Ks (Easy)
|
ユーザー |
![]() |
提出日時 | 2022-03-25 22:19:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 297 ms / 2,000 ms |
コード長 | 1,028 bytes |
コンパイル時間 | 1,917 ms |
コンパイル使用メモリ | 197,992 KB |
最終ジャッジ日時 | 2025-01-28 12:15:20 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; int main(){ int N, M; cin >> N >> M; vector<vector<long long>> dp(N + 1, vector<long long>(M + 1, 0)); for (int i = 1; i <= M; i++){ for (int j = 1; j < i; j++){ if (j <= N){ dp[j][i]++; } } } vector<vector<long long>> dpsum(N + 2, vector<long long>(M + 1, 0)); vector<long long> sum(N + 2, 0); for (int i = 1; i <= N; i++){ sum[i + 1] = sum[i]; for (int j = 1; j <= M; j++){ dpsum[i + 1][j] = dpsum[i][j]; int k = max(i - j + 1, 0); dp[i][j] += sum[i] - sum[k] + MOD; dp[i][j] -= dpsum[i][j] - dpsum[k][j]; dp[i][j] += MOD; dp[i][j] %= MOD; sum[i + 1] += dp[i][j]; sum[i + 1] %= MOD; dpsum[i + 1][j] += dp[i][j]; dpsum[i + 1][j] %= MOD; } } long long ans = 1; for (int i = 0; i < N; i++){ ans *= M; ans %= MOD; } for (int i = 1; i <= M; i++){ ans += MOD - dp[N][i]; ans %= MOD; } cout << ans << endl; }