test/aoj/0168.test.cpp

• View this file on GitHub
• Last update: 2020-12-20 13:43:34+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168

Depends on

• convolution/naive.cpp
• math/bostanmori.cpp

Code

// 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;
}

Back to top page