結果
問題 | No.1011 Infinite Stairs |
ユーザー | shibh308 |
提出日時 | 2020-03-20 21:30:12 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,371 bytes |
コンパイル時間 | 2,146 ms |
コンパイル使用メモリ | 204,780 KB |
実行使用メモリ | 432,820 KB |
最終ジャッジ日時 | 2023-08-21 15:20:56 |
合計ジャッジ時間 | 8,368 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 26 ms
8,876 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 382 ms
51,316 KB |
testcase_05 | TLE | - |
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 i64 = long long; const i64 MOD = 1e9 + 7; const i64 INF = i64(1e18) + 7; template <typename T> bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } template <typename T> bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template <i64 mod = MOD> struct ModInt{ i64 p; ModInt() : p(0){} ModInt(i64 x){p = x >= 0 ? x % mod : x + (-x + mod - 1) / mod * mod;} ModInt& operator+=(const ModInt& y){p = p + *y - ((p + *y) >= mod ? mod : 0); return *this;} ModInt& operator-=(const ModInt& y){p = p - *y + (p - *y < 0 ? mod : 0); return *this;} ModInt& operator*=(const ModInt& y){p = (p * *y) % mod; return *this;} ModInt& operator%=(const ModInt& y){if(y)p %= *y; return *this;} ModInt operator+(const ModInt& y) const{ModInt x = *this; return x += y;} ModInt operator-(const ModInt& y) const{ModInt x = *this; return x -= y;} ModInt operator*(const ModInt& y) const{ModInt x = *this; return x *= y;} ModInt operator%(const ModInt& y) const{ModInt x = *this; return x %= y;} friend ostream& operator<<(ostream& stream, const ModInt<mod>& x){ stream << *x; return stream; } friend ostream& operator>>(ostream& stream, const ModInt<mod>& x){ stream >> *x; return stream; } ModInt& operator++(){p = (p + 1) % mod; return *this;} ModInt& operator--(){p = (p - 1 + mod) % mod; return *this;} bool operator==(const ModInt& y) const{return p == *y;} bool operator!=(const ModInt& y) const{return p != *y;} const i64& operator*() const{return p;} i64& operator*(){return p;} }; using mint = ModInt<>; template <typename T> struct Matrix{ int h, w; vector<T> v; Matrix() : h(1), w(1), v(1, 1){} Matrix(int n){*this = makeUnit(n);} Matrix(int h, int w) : h(h), w(w), v(h * w, 0){} Matrix(vector<vector<T>> v_) : h(v_.size()), w(v_[0].size()), v(h * w){ for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) v[i * w + j] = v_[i][j]; } static Matrix makeUnit(int n){ Matrix mat(n, n); for(int i = 0; i < n; ++i) mat.at(i, i) = 1; return mat; } T& at(int i, int j){ assert(0 <= i && i <= h && 0 <= j && j < w); return v[i * w + j]; }; Matrix pow(i64 x){ assert(h == w); auto mat = x & 1 ? *this : makeUnit(h); auto u = *this; while(u = u * u, x >>= 1) if(x & 1) mat *= u; return mat; } Matrix& operator+=(const Matrix& mat){ assert(h == mat.h && w == mat.w); for(int i = 0; i < h * w; ++i) v[i] += mat.v[i]; return *this; } Matrix& operator-=(const Matrix& mat){ assert(h == mat.h && w == mat.w); for(int i = 0; i < h * w; ++i) v[i] -= mat.v[i]; return *this; } Matrix& operator%=(const T mod){ for(int i = 0; i < h * w; ++i) v[i] %= mod; return *this; } Matrix operator*(const Matrix& mat){ assert(w == mat.h); Matrix ret(h, mat.w); for(int i = 0; i < h; ++i) for(int k = 0; k < w; ++k) for(int j = 0; j < mat.w; ++j) ret.v[i * mat.w + j] += v[i * w + k] * mat.v[k * mat.w + j]; return ret; } Matrix operator+(const Matrix& mat){return Matrix(*this) += mat;} Matrix operator-(const Matrix& mat){return Matrix(*this) -= mat;} Matrix operator%(const T mod){return Matrix(*this) %= mod;} Matrix& operator*=(const Matrix& mat){return *this = *this * mat;} }; template<typename T> struct Segtree{ int n; T op; vector<T> elm; function<T(T, T)> f; Segtree(int n, T init, function<T(T, T)> f, T op = T()) : n(n), op(op), elm(2 * n, init), f(f) { for(int i = n - 1; i >= 1; --i) elm[i] = f(elm[2 * i], elm[2 * i + 1]); } Segtree(int n, vector<T> init, function<T(T, T)> f, T op = T()) : n(n), op(op), elm(2 * n), f(f) { for(int i = 0; i < n; ++i) elm[i + n] = init[i]; for(int i = n - 1; i >= 1; --i) elm[i] = f(elm[2 * i], elm[2 * i + 1]); } void set(int x, T val){ x += n; elm[x] = val; while(x >>= 1) elm[x] = f(elm[2 * x], elm[2 * x + 1]); } void update(int x, T val){ x += n; elm[x] = f(elm[x], val); while(x >>= 1) elm[x] = f(elm[2 * x], elm[2 * x + 1]); } T get(int x, int y) const{ T l = op, r = op; for(x += n, y += n - 1; x <= y; x >>= 1, y >>= 1){ if(x & 1) l = f(l, elm[x++]); if(!(y & 1)) r = f(elm[y--], r); } return f(l, r); } }; signed main(){ int n, d, k; cin >> n >> d >> k; vector<Segtree<mint>> dp(n + 1, Segtree<mint>(k + 1, 0, [](auto x, auto y){return x + y;}, 0LL)); dp[0].set(0, 1); for(int i = 0; i < n; ++i) for(int j = 0; j <= k; ++j) dp[i + 1].update(j, dp[i].get(max(0, j - d), j)); cout << dp.back().get(k, k + 1) << endl; return 0; }