結果
問題 | No.1011 Infinite Stairs |
ユーザー |
![]() |
提出日時 | 2020-03-27 22:26:41 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 276 ms / 2,000 ms |
コード長 | 1,875 bytes |
コンパイル時間 | 2,118 ms |
コンパイル使用メモリ | 164,744 KB |
実行使用メモリ | 215,044 KB |
最終ジャッジ日時 | 2024-07-17 12:03:39 |
合計ジャッジ時間 | 4,038 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> //#include "bits/stdc++.h" using namespace std; typedef long long ll; //#include "boost/multiprecision/cpp_int.hpp" //typedef boost::multiprecision::cpp_int ll; typedef long double dd; #define i_7 (ll)(1E9+7) //#define i_7 998244353 #define i_5 i_7-2 ll mod(ll a){ ll c=a%i_7; if(c>=0)return c; return c+i_7; } typedef pair<ll,ll> l_l; typedef pair<dd,dd> d_d; ll inf=(ll)1E16; #define rep(i,l,r) for(ll i=l;i<=r;i++) #define pb push_back ll max(ll a,ll b){if(a<b)return b;else return a;} ll min(ll a,ll b){if(a>b)return b;else return a;} void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]); void Min(ll &pos,ll val){pos=min(pos,val);} void Add(ll &pos,ll val){pos=mod(pos+val);} dd EPS=1E-9; #define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define fi first #define se second #define endl "\n" #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //template<class T>void max(T a,T b){if(a<b)return b;else return a;} //template<class T>void min(T a,T b){if(a>b)return b;else return a;} //template<class T>bool Max(T&a, T b){if(a < b){a = b;return 1;}return 0;} //template<class T>bool Min(T&a, T b){if(a > b){a = b;return 1;}return 0;} ////////////////////////// int main(){fastio ll n,d,k;cin>>n>>d>>k; ll dp[n+1][k+1];memset(dp,0,sizeof(dp)); rep(i,0,k)dp[0][i]=1; rep(i,1,n){ dp[i][0]=0; rep(j,1,k){ dp[i][j]=dp[i-1][j-1]; if(j-d-1>=0)Add(dp[i][j],-dp[i-1][j-d-1]); } rep(j,1,k)Add(dp[i][j],dp[i][j-1]); } /* rep(i,0,n){ rep(j,0,k)cout<<dp[i][j]<<" ";cout<<endl; }*/ cout<<mod(dp[n][k]-dp[n][k-1])<<endl; return 0; }