結果
問題 |
No.1011 Infinite Stairs
|
ユーザー |
![]() |
提出日時 | 2020-03-20 21:45:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 310 ms / 2,000 ms |
コード長 | 3,877 bytes |
コンパイル時間 | 1,820 ms |
コンパイル使用メモリ | 173,100 KB |
実行使用メモリ | 227,564 KB |
最終ジャッジ日時 | 2024-07-17 11:47:04 |
合計ジャッジ時間 | 4,226 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD=1e9+7; template<uint_fast64_t Modulus> class modint{ using u64=uint_fast64_t; public: u64 a; constexpr modint(const u64 x=0) noexcept:a(((x%Modulus)+Modulus)%Modulus){} constexpr u64 &value() noexcept{return a;} constexpr const u64 &value() const noexcept{return a;} constexpr modint &operator+=(const modint &rhs) noexcept{ a+=rhs.a; if (a>=Modulus) a-=Modulus; return *this; } constexpr modint operator+(const modint &rhs) const noexcept{ return modint(*this)+=rhs; } constexpr modint &operator++() noexcept{ return ++a,*this; } constexpr modint operator++(int) noexcept{ modint t=*this; return ++a,t; } constexpr modint &operator-=(const modint &rhs) noexcept{ if (a<rhs.a) a+=Modulus; a-=rhs.a; return *this; } constexpr modint operator-(const modint &rhs) const noexcept{ return modint(*this)-=rhs; } constexpr modint &operator--() noexcept{ return --a,*this; } constexpr modint operator--(int) noexcept{ modint t=*this; return --a,t; } constexpr modint &operator*=(const modint &rhs) noexcept{ a=a*rhs.a%Modulus; return *this; } constexpr modint operator*(const modint &rhs) const noexcept{ return modint(*this)*=rhs; } constexpr modint &operator/=(modint rhs) noexcept{ u64 exp=Modulus-2; while(exp){ if (exp&1) *this*=rhs; rhs*=rhs; exp>>=1; } return *this; } constexpr modint operator/(const modint &rhs) const noexcept{ return modint(*this)/=rhs; } constexpr modint operator-() const noexcept{ return modint(Modulus-a); } constexpr bool operator==(const modint &rhs) const noexcept{ return a==rhs.a; } constexpr bool operator!=(const modint &rhs) const noexcept{ return a!=rhs.a; } constexpr bool operator!() const noexcept{return !a;} friend constexpr modint pow(modint rhs,long long exp) noexcept{ modint res{1}; while(exp){ if (exp&1) res*=rhs; rhs*=rhs; exp>>=1; } return res; } template<class T> friend constexpr modint operator+(T x,modint y) noexcept{ return modint(x)+y; } template<class T> friend constexpr modint operator-(T x,modint y) noexcept{ return modint(x)-y; } template<class T> friend constexpr modint operator*(T x,modint y) noexcept{ return modint(x)*y; } template<class T> friend constexpr modint operator/(T x,modint y) noexcept{ return modint(x)/y; } friend ostream &operator<<(ostream &s,const modint &rhs) noexcept { return s << rhs.a; } friend istream &operator>>(istream &s,modint &rhs) noexcept { u64 a; rhs=modint{(s >> a,a)}; return s; } }; using mint=modint<MOD>; const int MAX=5e5+10; vector<mint> fac(MAX),finv(MAX),inv(MAX); void COMinit(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for (int i=2;i<MAX;++i){ fac[i]=fac[i-1]*i; inv[i]=-inv[MOD%i]*(MOD/i); finv[i]=finv[i-1]*inv[i]; } } mint COM(int n,int k){ if (n<k||n<0||k<0) return 0; return fac[n]*finv[k]*finv[n-k]; } //Be careful with the value of MAX and conducting COMinit() int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,d,K; cin >> N >> d >> K; vector<vector<mint>> dp(N+1,vector<mint>(K+1,0)); vector<mint> sum(K+2,1); dp[0][0]=1; sum[0]=0; for (int i=0;i<N;++i){ for (int j=K;j>=0;--j){ dp[i+1][j]+=sum[j]-sum[max(0,j-d)]; sum[j+1]=dp[i+1][j]; } for (int j=0;j<K+1;++j) sum[j+1]+=sum[j]; } cout << dp[N][K] << '\n'; }