Codeforces1716 D. Chip Move（dp，步长大于1的前缀和优化）

题意：

解法：

由于第i步必须走k-i+1的倍数,
因此k步至少走1+2+3+....+k=k*(k+1)/2步
所以走的步数是O(sq)级别的.

令d[i][j]表示i步走到j的方案数
转移方程:
令k=k+i-1
d[i][j]=d[i-1][j-t]+d[i-1][j-t*2]....

这里d[i-1][j-k*t]可以用前缀和优化.
预处理一个sum[j]=d[i-1][j]+sum[j-t]即可.
复杂度O(sq*n)

Code：

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
// #define int long long
#define PI pair<int, int>
const int maxm=2e5+5;
const int mod=998244353;
int n,k;
int d[2][maxm];
int sum[maxm];
int ans[maxm];
void MOD(int& x){
  if(x>=mod)x-=mod;
}
void solve(){
  cin>>n>>k;
  int x=0,y=1;
  d[x][0]=1;
  // 计算最多走多少次
  // len*(len+1)/2<=n
  int len=sqrt(n*2)+1;
  for(int i=1;i<=len;i++){
    int step=k+i-1;
    // 预处理前缀和
    for(int j=0;j<=n;j++){
      sum[j]=d[x][j];
      if(j-step>=0)MOD(sum[j]+=sum[j-step]);
    }
    for(int j=0;j<=n;j++)d[y][j]=0;
    // dp
    for(int j=step;j<=n;j++){
      d[y][j]=sum[j-step];
      MOD(ans[j]+=d[y][j]);
    }
    swap(x,y);
  }
  for(int i=1;i<=n;i++){
    cout<<ans[i]<<' ';
  }
}
signed main() {
// #define MULTI_CASE
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("../in.txt", "r", stdin);
  freopen("../out.txt", "w", stdout);
#endif
#ifdef MULTI_CASE
  int T;
  cin >> T;
  while (T--)
#endif
    solve();
  return 0;
}

---