結果
問題 | No.2791 Beginner Contest |
ユーザー |
![]() |
提出日時 | 2024-07-09 20:56:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 3,040 bytes |
コンパイル時間 | 1,686 ms |
コンパイル使用メモリ | 170,668 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-09 20:56:21 |
合計ジャッジ時間 | 2,823 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define int long long#define ld long double#define rep(i, n) for (int i = 0; i < n; i++)#define ll long long#define rep(i, n) for (int i = 0; i < n; i++)template <long long mod> struct modint {modint(ll v = 0) : value(normalize(v)) {}ll val() const { return value; }void normalize() { value = normalize(value); }ll normalize(ll v) {if (v <= mod && v >= -mod) {if (v < 0)v += mod;return v;}if (v > 0 && v < 2 * mod) {v -= mod;return v;}if (v < 0 && v > -2 * mod) {v += 2 * mod;return v;}v %= mod;if (v < 0)v += mod;return v;}modint<mod> &operator=(ll v) {value = normalize(v);return *this;}bool operator==(const modint &o) const { return value == o.val(); }bool operator!=(const modint &o) const { return value != o.val(); }const modint &operator+() const { return *this; }const modint &operator-() const { return value ? mod - value : 0; }const modint operator+(const modint &o) const { return value + o.val(); }modint &operator+=(const modint &o) {value += o.val();if (value >= mod)value -= mod;return *this;}const modint operator-(const modint &o) const { return value - o.val(); }modint &operator-=(const modint &o) {value -= o.val();if (value < 0)value += mod;return *this;}const modint operator*(const modint &o) const {return (value * o.val()) % mod;}modint &operator*=(const modint &o) {value *= o.val();value %= mod;return *this;}const modint operator/(const modint &o) const { return operator*(o.inv()); }modint &operator/=(const modint &o) { return operator*=(o.inv()); }const modint pow(ll n) const {modint ans = 1, x(value);while (n > 0) {if (n & 1)ans *= x;x *= x;n >>= 1;}return ans;}const modint inv() const {ll a = value, b = mod, u = 1, v = 0;while (b) {ll t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}return u;}friend ostream &operator<<(ostream &os, const modint &x) {return os << x.val();}template <typename T> friend modint operator+(T t, const modint &o) {return o + t;}template <typename T> friend modint operator-(T t, const modint &o) {return -o + t;}template <typename T> friend modint operator*(T t, const modint &o) {return o * t;}template <typename T> friend modint operator/(T t, const modint &o) {return o.inv() * t;}private:ll value;};using mint = modint<998244353>;signed main() {int n, k;cin >> n >> k;mint ans = 0;vector<mint> a(2e5 + 2);int cnt = 1;a[0] = 1;rep(i, 2e5 + 2) {if (i == 0)continue;a[i] = a[i - 1] * i;}rep(i, n + 1) {int t = n - k * i;if (t < 0)continue;ans += mint(a[(t + i)]) / mint(a[t]) / mint(a[i]);}cout << ans << endl;}