結果

問題 No.2215 Slide Subset Sum
コンテスト
ユーザー Caiiiiiiii
提出日時 2026-08-26 22:59:09
言語 C++17
(gcc 15.3.0 + boost 1.92.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 195 ms / 3,000 ms
+ 245µs
コード長 955 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,028 ms
コンパイル使用メモリ 210,592 KB
実行使用メモリ 166,784 KB
最終ジャッジ日時 2026-08-26 22:59:23
合計ジャッジ時間 11,574 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using LL = long long;

const int N = 2e5 + 7;
const int K = 200 + 7;
const int MOD = 998244353;

int n, m, k;
int f[N][K], g[N][K], a[N], ans[N];

void dp(int *f, int *g, int x) {
  for(int i = 0; i < k; ++i)
    f[i] = (g[i] + g[(i + k - x) % k]) % MOD;
}

int main() {
  
  scanf("%d%d%d", &n, &m, &k);
  for(int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);

  f[0][0] = g[0][0] = 1;
  for(int i = m; i <= n; i += m) {
    for(int j = 1; j <= m; ++j)
      dp(f[j], f[j - 1], a[i - j + 1]);
    for(int j = 1; j + i < i + m && j + i <= n; ++j)
      dp(g[j], g[j - 1], a[i + j]);
    for(int j = i - m + 1; j + m - 1 <= n && j <= i; ++j) {
      ans[j] = 1LL * f[i - j + 1][0] * g[j + m - i - 1][0] % MOD;
      for(int t = 1; t < k; ++t) 
	ans[j] = (ans[j] + 1LL * f[i - j + 1][t] * g[j + m - i - 1][k - t]) % MOD;
    }
  }

  for(int i = 1; i <= n - m + 1; ++i)
    printf("%d\n", (ans[i] + MOD - 1) % MOD);
  
  return 0;
}
0