TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Distance Sequence

問題

E – Distance Sequence
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int MOD = 1000000007;
const int MOD = 998244353;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

// dp[i][j] := 長さ i+1 で最後が j である数列の個数
// i ... i+1 個まで作った
// k ... 1 から Mまで
// dp[i+1][j] = dp[i][1...M] - dp[i][j-k+1...j+k-1]
//            = sum[M] - (sum[r] - sum[l])
// r = min(M, j + K)
// l = max(0, j - K + 1)

int main() {
  int N, M, K;
  cin >> N >> M >> K;

  vector<vector<ll>> dp(N, vector<ll>(M));

  for(int i = 0; i < M; ++i) {
    dp[0][i] = 1;
  }

  for(int i = 0; i < N-1; ++i) {

    vector<ll> sum(M+1);
    for(int j = 0; j < M; ++j) {
      sum[j+1] = sum[j] + dp[i][j];
      sum[j] %= MOD;
    }

    for(int j = 0; j < M; ++j) {
      dp[i+1][j] = sum[M];
      if(0 < K) {
        int l = max(0, j-K+1);
        int r = min(M, j+K);
        dp[i+1][j] -= (sum[r] - sum[l]);
      }
      dp[i+1][j] %= MOD;
    }

  }

  // rep(i, N) {
  //   rep(j, M) {
  //     cout << dp[i][j] << " ";
  //   }
  //   cout << endl;
  // }

  ll ans = 0;
  for(int i = 0; i < M; ++i) {
    ans += dp[N-1][i];
    ans %= MOD;
  }

  cout << ans << endl;

  return 0;
}