This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168 #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../convolution/naive.cpp" #include "../../math/bostanmori.cpp" #undef call_from_test signed main(){ using ll = long long; BostanMori<ll> bm(naive<ll>()); using Poly = vector<ll>; Poly as({0,0,1}),cs({-1,-1,-1,1}); int n; while(cin>>n,n) cout<<(bm.build(n+2,as,cs)+3650-1)/3650<<endl; return 0; }
#line 1 "test/aoj/0168.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168 #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "convolution/naive.cpp" #line 3 "convolution/naive.cpp" using namespace std; #endif //BEGIN CUT HERE // O(N M) template<typename T> decltype(auto) naive(){ using Poly = vector<T>; auto conv=[](Poly as, Poly bs){ Poly cs(as.size()+bs.size()-1,0); for(int i=0;i<(int)as.size();i++) for(int j=0;j<(int)bs.size();j++) cs[i+j]+=as[i]*bs[j]; return cs; }; return +conv; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "math/bostanmori.cpp" #line 3 "math/bostanmori.cpp" using namespace std; #endif // ref. https://qiita.com/ryuhe1/items/da5acbcce4ac1911f47a //BEGIN CUT HERE // Find k-th term of linear recurrence // execute `conv` O(\log k) times template<typename T> struct BostanMori{ using Poly = vector<T>; using Conv = function<Poly(Poly, Poly)>; Conv conv; BostanMori(Conv conv_):conv(conv_){} Poly sub(Poly as,int odd){ Poly bs((as.size()+!odd)/2); for(int i=odd;i<(int)as.size();i+=2) bs[i/2]=as[i]; return bs; } // as: initial values // cs: monic polynomial T build(long long k,Poly as,Poly cs){ reverse(cs.begin(),cs.end()); assert(cs[0]==T(1)); int n=cs.size()-1; as.resize(n,0); Poly bs=conv(as,cs); bs.resize(n); while(k){ Poly ds(cs); for(int i=1;i<(int)ds.size();i+=2) ds[i]=-ds[i]; bs=sub(conv(bs,ds),k&1); cs=sub(conv(cs,ds),0); k>>=1; } return bs[0]; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 9 "test/aoj/0168.test.cpp" #undef call_from_test signed main(){ using ll = long long; BostanMori<ll> bm(naive<ll>()); using Poly = vector<ll>; Poly as({0,0,1}),cs({-1,-1,-1,1}); int n; while(cin>>n,n) cout<<(bm.build(n+2,as,cs)+3650-1)/3650<<endl; return 0; }