Advertisement
pb_jiang

ABC253E WA

Aug 15th, 2023
939
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. // Problem: E - Distance Sequence
  2. // Contest: AtCoder - NOMURA Programming Contest 2022(AtCoder Beginner Contest 253οΌ‰
  3. // URL: https://atcoder.jp/contests/abc253/tasks/abc253_e
  4. // Memory Limit: 1024 MB
  5. // Time Limit: 2000 ms
  6. //
  7. // Powered by CP Editor (https://cpeditor.org)
  8.  
  9. #include <assert.h>
  10. #include <bits/stdc++.h>
  11. #include <atcoder/modint>
  12. using namespace std;
  13. #ifndef __DEBUG__
  14. #define dbg(...) 42
  15. #endif
  16. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  17.  
  18. using ll = long long;
  19. using pii = pair<int, int>;
  20. using pll = pair<ll, ll>;
  21. using vl = vector<ll>;
  22. using vi = vector<int>;
  23. using mint = atcoder::modint998244353;
  24.  
  25. int main(int argc, char **argv)
  26. {
  27.     int n, m, k;
  28.     cin >> n >> m >> k;
  29.     vector<mint> dp(m, 1);
  30.     for (int i = 2; i <= n; ++i) {
  31.         vector<mint> ndp(m);
  32.         vector<mint> acc(m + 1);
  33.         for (int j = 0; j < m; ++j)
  34.             acc[j + 1] = acc[j] + dp[j];
  35.         for (int j = 0; j < m; ++j) {
  36.             if (j >= k)
  37.                 ndp[j] += acc[j - k + 1];
  38.             if (j + k <= m)
  39.                 ndp[j] += acc[m] - acc[j + k];
  40.         }
  41.  
  42.         dp.swap(ndp);
  43.     }
  44.     mint ans = 0;
  45.     for (auto x : dp)
  46.         ans += x;
  47.     cout << ans.val() << endl;
  48.     return 0;
  49. };
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement