結果
問題 | No.535 自然数の収納方法 |
ユーザー |
![]() |
提出日時 | 2017-04-16 22:54:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,284 bytes |
コンパイル時間 | 1,487 ms |
コンパイル使用メモリ | 171,216 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-19 04:06:45 |
合計ジャッジ時間 | 2,855 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long LL;#define CIN_ONLY if(1)struct cww{cww(){CIN_ONLY{ios::sync_with_stdio(false);cin.tie(0);}}}star;#define fin "\n"#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()#define fi first#define se second#define pb push_back#define DEBUG if(0)#define REC(ret, ...) std::function<ret (__VA_ARGS__)>template <typename T>inline bool chmin(T &l,T r){bool a=l>r;if(a)l=r;return a;}template <typename T>inline bool chmax(T &l,T r){bool a=l<r;if(a)l=r;return a;}template <typename T>istream& operator>>(istream &is,vector<T> &v){for(auto &it:v)is>>it;return is;}const int mod=1e9+7;vector<LL> count(LL N,vector<LL> ini){auto dp=ini;REP(i,N-1){REP(j,N-1)(dp[j+1]+=dp[j])%=mod;vector<LL> nxt(N,0);LL sa=max(i-1,0);REP(j,N){(nxt[j]+=dp[min(N-1,j+sa)])%=mod;}swap(dp,nxt);}return dp;}int main(){int N;cin>>N;vector<LL> S(N,0);S[0]=1;auto A = count(N,S);fill(ALL(S),1);auto B=count(N,S);LL res=0;for(auto &it:B)(res+=it)%=mod;(res+=mod-A.back())%=mod;cout<<res<<endl;return 0;}