結果
問題 | No.1011 Infinite Stairs |
ユーザー | kibuna |
提出日時 | 2020-03-20 21:37:53 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,747 bytes |
コンパイル時間 | 1,956 ms |
コンパイル使用メモリ | 170,660 KB |
実行使用メモリ | 9,776 KB |
最終ジャッジ日時 | 2023-08-21 15:47:38 |
合計ジャッジ時間 | 5,395 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
8,756 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 68 ms
4,380 KB |
testcase_03 | TLE | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; const lint inf = 1LL << 60; const lint mod = 1000000007; struct mint { lint v; lint _mod; mint() : v(0) {} mint(signed v, lint _mod = mod) : v(v), _mod(_mod) {} mint(lint t, lint _mod = mod) : _mod(_mod) { v = t % _mod; if (v < 0) v += _mod; } mint pow(lint k) { mint res(1), tmp(v); while (k) { if (k & 1) res *= tmp; tmp *= tmp; k >>= 1; } return res; } static mint add_identity() { return mint(0); } static mint mul_identity() { return mint(1); } mint inv() { return pow(_mod - 2); } mint &operator+=(mint a) { v += a.v; if (v >= _mod) v -= _mod; return *this; } mint &operator-=(mint a) { v += _mod - a.v; if (v >= _mod) v -= _mod; return *this; } mint &operator*=(mint a) { v = v * a.v % _mod; return *this; } mint &operator/=(mint a) { return (*this) *= a.inv(); } mint operator+(mint a) const { return mint(v) += a; }; mint operator-(mint a) const { return mint(v) -= a; }; mint operator*(mint a) const { return mint(v) *= a; }; mint operator/(mint a) const { return mint(v) /= a; }; mint operator-() const { return v ? mint(_mod - v) : mint(v); } bool operator==(const mint a) const { return v == a.v; } bool operator!=(const mint a) const { return v != a.v; } bool operator<(const mint a) const { return v < a.v; } }; ostream &operator<<(ostream &os, mint m) { return os << m.v; } // 0-indexed bottom up Segment Tree // UNIT is the identity element of operation func template <typename T = int> struct SegmentTree { using F = function<T(T, T)>; int n; vector<T> dat; F func; T UNIT; SegmentTree(int n_, F func_, T UNIT_) : func(func_), UNIT(UNIT_) { n = 1; // full binary tree: num of leaves = n = 2^k >= n_ while (n < n_) n *= 2; dat.assign(2 * n - 1, UNIT); } SegmentTree(vector<T> v_, F func_, T UNIT_) : func(func_), UNIT(UNIT_) { n = 1; int nv = v_.size(); while (n < nv) n *= 2; dat.assign(2 * n - 1, UNIT); for (int i = 0; i < nv; ++i) { dat[n - 1 + i] = v_[i]; } for (int i = n - 2; i >= 0; --i) { dat[i] = func(dat[2 * i + 1], dat[2 * i + 2]); } } void update(int k, T a) { // leaves are at index n-1 to 2*n-2 k += n - 1; dat[k] = a; while (k > 0) { // k -> parent node k = (k - 1) / 2; // func(child nodes) dat[k] = func(dat[2 * k + 1], dat[2 * k + 2]); } } // get result of func() in [l, r) T query(int l, int r) { l += n - 1; r += n - 1; T retl = UNIT, retr = UNIT; while (l < r) { if ((l & 1) == 0) retl = func(retl, dat[l]); if ((r & 1) == 0) retr = func(dat[r - 1], retr); l = l / 2; r = (r - 1) / 2; } return func(retl, retr); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); lint n, d, k; cin >> n >> d >> k; auto f = [](mint l, mint r) { return l + r; }; const mint unit = 0; SegmentTree<mint> st(k + 1, f, unit); st.update(0, 1); for (int i = 0; i < n; ++i) { for (int j = k; j >= 0; --j) { mint v = st.query(max(0LL, j - d), j); st.update(j, v); } } cout << st.query(k, k + 1) << "\n"; return 0; }