結果
問題 | No.2791 Beginner Contest |
ユーザー | ななな |
提出日時 | 2024-07-09 20:56:18 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,376 KB |
testcase_02 | AC | 6 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 4 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 5 ms
5,376 KB |
testcase_07 | AC | 4 ms
5,376 KB |
testcase_08 | AC | 4 ms
5,376 KB |
testcase_09 | AC | 4 ms
5,376 KB |
testcase_10 | AC | 5 ms
5,376 KB |
testcase_11 | AC | 4 ms
5,376 KB |
testcase_12 | AC | 12 ms
5,376 KB |
testcase_13 | AC | 4 ms
5,376 KB |
testcase_14 | AC | 4 ms
5,376 KB |
testcase_15 | AC | 4 ms
6,940 KB |
testcase_16 | AC | 3 ms
6,940 KB |
testcase_17 | AC | 3 ms
6,944 KB |
testcase_18 | AC | 4 ms
6,944 KB |
testcase_19 | AC | 4 ms
6,940 KB |
ソースコード
#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; }