結果
問題 | No.2791 Beginner Contest |
ユーザー |
![]() |
提出日時 | 2024-06-21 21:32:50 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 3,215 bytes |
コンパイル時間 | 2,051 ms |
コンパイル使用メモリ | 202,248 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-21 21:32:53 |
合計ジャッジ時間 | 2,916 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define all(v) (v).begin(),(v).end()#define pb(a) push_back(a)#define rep(i, n) for(int i=0;i<n;i++)#define foa(e, v) for(auto& e : v)using ll = long long;const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;template<int MOD> struct Modint {long long val;constexpr Modint(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; }constexpr int mod() const { return MOD; }constexpr long long value() const { return val; }constexpr Modint operator - () const noexcept { return val ? MOD - val : 0; }constexpr Modint operator + (const Modint& r) const noexcept { return Modint(*this) += r; }constexpr Modint operator - (const Modint& r) const noexcept { return Modint(*this) -= r; }constexpr Modint operator * (const Modint& r) const noexcept { return Modint(*this) *= r; }constexpr Modint operator / (const Modint& r) const noexcept { return Modint(*this) /= r; }constexpr Modint& operator += (const Modint& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Modint& operator -= (const Modint& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Modint& operator *= (const Modint& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Modint& operator /= (const Modint& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Modint& r) const noexcept { return this->val == r.val; }constexpr bool operator != (const Modint& r) const noexcept { return this->val != r.val; }friend constexpr istream& operator >> (istream& is, Modint<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Modint<MOD>& x) noexcept {return os << x.val;}constexpr Modint<MOD> pow(long long n) noexcept {if (n == 0) return 1;if (n < 0) return this->pow(-n).inv();Modint<MOD> ret = pow(n >> 1);ret *= ret;if (n & 1) ret *= *this;return ret;}constexpr Modint<MOD> inv() const noexcept {long long a = this->val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return Modint<MOD>(u);}};const int MOD = MOD998;using mint = Modint<MOD>;int main() {cin.tie(0);ios::sync_with_stdio(false);ll n, k;cin >> n >> k;vector<mint> dp(n + 1, mint(0));dp[0] = 1;mint sum = 0, ans = 1;for(int i = 1; i <= n; i ++) {if(i >= k) sum += dp[i - k];dp[i] = sum;ans += dp[i];}cout << ans << endl;return 0;}