結果
問題 |
No.1011 Infinite Stairs
|
ユーザー |
👑 |
提出日時 | 2020-03-20 23:46:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 2,009 bytes |
コンパイル時間 | 647 ms |
コンパイル使用メモリ | 65,000 KB |
実行使用メモリ | 109,352 KB |
最終ジャッジ日時 | 2024-07-17 11:55:42 |
合計ジャッジ時間 | 2,536 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <iostream> using namespace std; const int mod = 1000000007; template <int mod> struct ModInt{ int n; ModInt():n(0){} ModInt(int n_):n(n_ >= 0 ? n_%mod : mod - ((-n_)%mod) ){} ModInt &operator+=(const ModInt &p){ if((n+=p.n) >= mod)n-=mod; return *this; } ModInt &operator-=(const ModInt &p){ n+=mod-p.n; if(n >= mod)n-=mod; return *this; } ModInt &operator*=(const ModInt &p){ n = (int) ((1LL*n*p.n)%mod); return *this; } ModInt &operator/=(const ModInt &p){ *this *= p.inverse(); return *this; } ModInt operator-() const {return ModInt(-n);} ModInt operator+(const ModInt &p) const {return ModInt(*this) += p;} ModInt operator-(const ModInt &p) const {return ModInt(*this) -= p;} ModInt operator*(const ModInt &p) const {return ModInt(*this) *= p;} ModInt operator/(const ModInt &p) const {return ModInt(*this) /= p;} bool operator==(const ModInt &p) const {return n==p.n;} bool operator!=(const ModInt &p) const {return n!=p.n;} ModInt inverse() const { int a = n,b = mod,u = 1,v = 0; while(b){ int t = a/b; a -= t*b; swap(a,b); u -= t*v; swap(u,v); } return ModInt(u); } ModInt pow(int64_t z) const { ModInt ret(1),mul(n); while(z > 0){ if(z & 1) ret *= mul; mul *= mul; z >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p){ return os << p.n; } friend istream &operator>>(istream &is, ModInt &a){ int64_t t; is >> t; a = ModInt<mod> (t); return (is); } }; using mint = ModInt<mod>; mint dp[301][90001]; __attribute__((constructor)) void initial() { cin.tie(0); ios::sync_with_stdio(false); } int main(){ int n,d,k;cin>>n>>d>>k; dp[0][0]=1; dp[0][1]=-1; for(int i = 0; n > i; i++){ mint nw = 0; for(int j = 0; k > j; j++){ nw+=dp[i][j]; dp[i+1][j+1]+=nw; dp[i+1][j+d+1]-=nw; } } mint nw = 0; for(int j = 0; k >= j; j++){ nw+=dp[n][j]; } cout << nw << endl; }