#409550 (C++17) No.696 square1001 and Permutation 5

• 問題: No.696 square1001 and Permutation 5
• ユーザー: beet
• 提出日時: 2019-12-17 20:42:03
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 519 ms / 10,000 ms
• コード長: 17,438 bytes
• コンパイル時間: 3,053 ms
• コンパイル使用メモリ: 230,296 KB
• 実行使用メモリ: 14,840 KB
• 最終ジャッジ日時: 2024-07-04 13:57:27
• 合計ジャッジ時間: 5,997 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	501 ms; 14,840 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	4 ms; 5,376 KB
testcase_05	AC	8 ms; 5,376 KB
testcase_06	AC	19 ms; 5,376 KB
testcase_07	AC	42 ms; 5,376 KB
testcase_08	AC	93 ms; 6,040 KB
testcase_09	AC	236 ms; 9,480 KB
testcase_10	AC	519 ms; 14,544 KB
testcase_11	AC	380 ms; 13,288 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB

ソースコード

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
namespace FFT{
  using dbl = double;

  struct num{
    dbl x,y;
    num(){x=y=0;}
    num(dbl x,dbl y):x(x),y(y){}
  };

  inline num operator+(num a,num b){
    return num(a.x+b.x,a.y+b.y);
  }
  inline num operator-(num a,num b){
    return num(a.x-b.x,a.y-b.y);
  }
  inline num operator*(num a,num b){
    return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
  }
  inline num conj(num a){
    return num(a.x,-a.y);
  }

  int base=1;
  vector<num> rts={{0,0},{1,0}};
  vector<int> rev={0,1};

  const dbl PI=asinl(1)*2;

  void ensure_base(int nbase){
    if(nbase<=base) return;

    rev.resize(1<<nbase);
    for(int i=0;i<(1<<nbase);i++)
      rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1));

    rts.resize(1<<nbase);
    while(base<nbase){
      dbl angle=2*PI/(1<<(base+1));
      for(int i=1<<(base-1);i<(1<<base);i++){
        rts[i<<1]=rts[i];
        dbl angle_i=angle*(2*i+1-(1<<base));
        rts[(i<<1)+1]=num(cos(angle_i),sin(angle_i));
      }
      base++;
    }
  }

  void fft(vector<num> &as){
    int n=as.size();
    assert((n&(n-1))==0);

    int zeros=__builtin_ctz(n);
    ensure_base(zeros);
    int shift=base-zeros;
    for(int i=0;i<n;i++)
      if(i<(rev[i]>>shift))
        swap(as[i],as[rev[i]>>shift]);

    for(int k=1;k<n;k<<=1){
      for(int i=0;i<n;i+=2*k){
        for(int j=0;j<k;j++){
          num z=as[i+j+k]*rts[j+k];
          as[i+j+k]=as[i+j]-z;
          as[i+j]=as[i+j]+z;
        }
      }
    }
  }

  template<typename T>
  vector<long long> multiply(vector<T> &as,vector<T> &bs){
    int need=as.size()+bs.size()-1;
    int nbase=0;
    while((1<<nbase)<need) nbase++;
    ensure_base(nbase);

    int sz=1<<nbase;
    vector<num> fa(sz);
    for(int i=0;i<sz;i++){
      T x=(i<(int)as.size()?as[i]:0);
      T y=(i<(int)bs.size()?bs[i]:0);
      fa[i]=num(x,y);
    }
    fft(fa);

    num r(0,-0.25/sz);
    for(int i=0;i<=(sz>>1);i++){
      int j=(sz-i)&(sz-1);
      num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r;
      if(i!=j)
        fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r;
      fa[i]=z;
    }
    fft(fa);

    vector<long long> res(need);
    for(int i=0;i<need;i++)
      res[i]=round(fa[i].x);

    return res;
  }

};
//END CUT HERE
#ifndef call_from_test
signed main(){
  int n;
  cin>>n;
  vector<int> as(n+1,0),bs(n+1,0);
  for(int i=1;i<=n;i++) cin>>as[i]>>bs[i];
  auto cs=FFT::multiply(as,bs);
  for(int i=1;i<=n*2;i++) cout<<cs[i]<<"\n";
  return 0;
}
/*
  verified on 2019/12/17
  https://atcoder.jp/contests/atc001/tasks/fft_c
*/
#endif

#undef call_from_test

#endif
//BEGIN CUT HERE
struct bigint {
  using ll = long long;
  using vll = vector<ll>;

  constexpr static ll base = 1000000000;
  constexpr static ll base_digits = 9;

  vll a;
  ll sign;

  bigint():sign(1){}

  bigint(ll v){*this=v;}

  bigint(const string &s){read(s);}

  static bigint add_identity(){return bigint(0);}
  static bigint mul_identity(){return bigint(1);}

  void operator=(ll v){
    sign=1;
    if(v<0) sign=-1,v=-v;
    for(;v>0;v=v/base) a.push_back(v%base);
  }

  bigint operator+(const bigint &v) const{
    if(sign==v.sign){
      bigint res=v;

      for(ll i=0,carry=0;i<(ll)max(a.size(),v.a.size())||carry;++i){
        if(i==(ll)res.a.size()) res.a.push_back(0);
        res.a[i]+=carry+(i<(ll)a.size()?a[i]:0);
        carry=res.a[i]>=base;
        if(carry) res.a[i]-=base;
      }
      return res;
    }
    return *this -(-v);
  }

  bigint operator-(const bigint &v) const{
    if(sign==v.sign){
      if(abs()>=v.abs()){
        bigint res=*this;
        for(ll i=0,carry=0;i<(ll)v.a.size()||carry;++i){
          res.a[i]-=carry+(i<(ll)v.a.size()?v.a[i]:0);
          carry=res.a[i]<0;
          if(carry) res.a[i]+=base;
        }
        res.trim();
        return res;
      }
      return -(v-*this);
    }
    return *this+(-v);
  }

  void operator*=(ll v){
    if(v<0) sign=-sign,v=-v;
    for(ll i=0,carry=0;i<(ll)a.size()|| carry;++i){
      if(i ==(ll)a.size()) a.push_back(0);
      ll cur=a[i] *(ll)v+carry;
      carry=(ll)(cur/base);
      a[i]=(ll)(cur%base);
      // asm("divl %%ecx" : "=a"(carry),"=d"(a[i]) : "A"(cur),"c"(base));
    }
    trim();
  }

  bigint operator*(ll v) const{
    bigint res=*this;
    res *=v;
    return res;
  }

  friend pair<bigint,bigint> divmod(const bigint &a1,const bigint &b1){
    ll norm=base/(b1.a.back()+1);
    bigint a=a1.abs()*norm;
    bigint b=b1.abs()*norm;
    bigint q,r;
    q.a.resize(a.a.size());

    for(ll i=a.a.size()-1;i>=0;i--){
      r *=base;
      r+=a.a[i];
      ll s1=r.a.size()<=b.a.size() ? 0 : r.a[b.a.size()];
      ll s2=r.a.size()<=b.a.size()-1 ? 0 : r.a[b.a.size()-1];
      ll d=((ll)base*s1+s2)/b.a.back();
      r-=b*d;
      while(r<0) r+=b,--d;
      q.a[i]=d;
    }

    q.sign=a1.sign*b1.sign;
    r.sign=a1.sign;
    q.trim();
    r.trim();
    return make_pair(q,r/norm);
  }

  bigint operator/(const bigint &v) const{
    return divmod(*this,v).first;
  }

  bigint operator%(const bigint &v) const{
    return divmod(*this,v).second;
  }

  void operator/=(ll v){
    if(v<0) sign=-sign,v=-v;
    for(ll i=(ll)a.size()-1,rem=0;i>=0;--i){
      ll cur=a[i]+rem *(ll)base;
      a[i]=(ll)(cur/v);
      rem=(ll)(cur%v);
    }
    trim();
  }

  bigint operator/(ll v) const{
    bigint res=*this;
    res/=v;
    return res;
  }

  ll operator%(ll v) const{
    if(v<0) v=-v;
    ll m=0;
    for(ll i=a.size()-1;i>=0;--i) m=(a[i]+m *(ll)base)%v;
    return m*sign;
  }

  void operator+=(const bigint &v){
    *this=*this+v;
  }

  void operator-=(const bigint &v){
    *this=*this-v;
  }

  void operator*=(const bigint &v){
    *this=*this*v;
  }

  void operator/=(const bigint &v){
    *this=*this/v;
  }

  bool operator<(const bigint &v) const{
    if(sign!=v.sign) return sign<v.sign;
    if(a.size()!=v.a.size()) return a.size()*sign<v.a.size()*v.sign;
    for(ll i=a.size()-1;i>=0;i--)
      if(a[i]!=v.a[i]) return a[i]*sign<v.a[i]*sign;
    return false;
  }

  bool operator>(const bigint &v) const{
    return v<*this;
  }

  bool operator<=(const bigint &v) const{
    return !(v<*this);
  }

  bool operator>=(const bigint &v) const{
    return !(*this<v);
  }

  bool operator==(const bigint &v) const{
    return !(*this<v)&&!(v<*this);
  }

  bool operator!=(const bigint &v) const{
    return *this<v|| v<*this;
  }

  void trim(){
    while(!a.empty()&&!a.back()) a.pop_back();
    if(a.empty()) sign=1;
  }

  bool isZero() const{
    return a.empty()||(a.size()==1&&!a[0]);
  }

  bigint operator-() const{
    bigint res=*this;
    res.sign=-sign;
    return res;
  }

  bigint abs() const{
    bigint res=*this;
    res.sign*=res.sign;
    return res;
  }

  ll longValue() const{
    ll res=0;
    for(ll i=a.size()-1;i>=0;i--) res=res*base+a[i];
    return res*sign;
  }

  friend bigint gcd(const bigint &a,const bigint &b){
    return b.isZero() ? a : gcd(b,a%b);
  }

  friend bigint lcm(const bigint &a,const bigint &b){
    return a/gcd(a,b)*b;
  }

  void read(const string &s){
    sign=1;
    a.clear();
    ll pos=0;
    while(pos<(ll)s.size()&&(s[pos]=='-'|| s[pos]=='+')){
      if(s[pos]=='-') sign=-sign;
      ++pos;
    }
    for(ll i=s.size()-1;i>=pos;i-=base_digits){
      ll x=0;
      for(ll j=max(pos,i-base_digits+1);j<=i;j++) x=x*10+s[j]-'0';
      a.push_back(x);
    }
    trim();
  }

  friend istream &operator>>(istream &stream,bigint &v){
    string s;
    stream>>s;
    v.read(s);
    return stream;
  }

  friend ostream &operator<<(ostream &stream,const bigint &v){
    if(v.sign==-1) stream<<'-';
    stream<<(v.a.empty()?0:v.a.back());
    for(ll i=(ll)v.a.size()-2;i>=0;--i)
      stream<<setw(base_digits)<<setfill('0')<<v.a[i];
    return stream;
  }

  static vll convert_base(const vll &a,ll old_digits,ll new_digits){
    vll p(max(old_digits,new_digits)+1);
    p[0]=1;
    for(ll i=1;i<(ll)p.size();i++) p[i]=p[i-1]*10;
    vll res;
    ll cur=0;
    ll cur_digits=0;
    for(ll i=0;i<(ll)a.size();i++){
      cur+=a[i]*p[cur_digits];
      cur_digits+=old_digits;
      while(cur_digits>=new_digits){
        res.push_back(signed(cur%p[new_digits]));
        cur/=p[new_digits];
        cur_digits-=new_digits;
      }
    }
    res.push_back((signed)cur);
    while(!res.empty()&&!res.back()) res.pop_back();
    return res;
  }

  static vll karatsubaMultiply(const vll &a,const vll &b){
    ll n=a.size();
    vll res(n+n);
    if(n<=32){
      for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
          res[i+j]+=a[i]*b[j];
      return res;
    }

    ll k=n>>1;
    vll a1(a.begin(),a.begin()+k);
    vll a2(a.begin()+k,a.end());
    vll b1(b.begin(),b.begin()+k);
    vll b2(b.begin()+k,b.end());

    vll a1b1=karatsubaMultiply(a1,b1);
    vll a2b2=karatsubaMultiply(a2,b2);

    for(ll i=0;i<k;i++) a2[i]+=a1[i];
    for(ll i=0;i<k;i++) b2[i]+=b1[i];

    vll r=karatsubaMultiply(a2,b2);
    for(ll i=0;i<(ll)a1b1.size();i++) r[i]-=a1b1[i];
    for(ll i=0;i<(ll)a2b2.size();i++) r[i]-=a2b2[i];

    for(ll i=0;i<(ll)r.size();i++) res[i+k]+=r[i];
    for(ll i=0;i<(ll)a1b1.size();i++) res[i]+=a1b1[i];
    for(ll i=0;i<(ll)a2b2.size();i++) res[i+n]+=a2b2[i];
    return res;
  }

  bigint operator*(const bigint &v) const{
    constexpr static ll nbase = 10000;
    constexpr static ll nbase_digits = 4;

    vll a=convert_base(this->a,base_digits,nbase_digits);
    vll b=convert_base(v.a,base_digits,nbase_digits);

    /*/
    while(a.size()<b.size()) a.push_back(0);
    while(b.size()<a.size()) b.push_back(0);
    while(a.size() &(a.size()-1)) a.push_back(0),b.push_back(0);
    vll c=karatsubaMultiply(a,b);
    /*/
    if(a.empty()) a.push_back(0);
    if(b.empty()) b.push_back(0);
    vll c=FFT::multiply(a,b);
    //*/

    bigint res;
    res.sign=sign*v.sign;
    for(ll i=0,carry=0;i<(ll)c.size();i++){
      ll cur=c[i]+carry;
      res.a.push_back((ll)(cur%nbase));
      carry=(ll)(cur/nbase);
      if(i+1==(int)c.size()&&carry>0) c.push_back(0);
    }

    res.a=convert_base(res.a,nbase_digits,base_digits);
    res.trim();
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct BIT{
  int n;
  vector<T> bit;
  //1-indexed
  BIT(int n_):n(n_+1),bit(n,0){}

  T sum(int i){
    T s(0);
    for(int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }

  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }

  int lower_bound(int w){
    if(w<=0) return 0;
    int x=0,r=1;
    while(r<n) r<<=1;
    for(int k=r;k>0;k>>=1){
      if(x+k<=n&&bit[x+k]<w){
        w-=bit[x+k];
        x+=k;
      }
    }
    return x+1;
  }

  // [l, r)
  T query(int l,int r){
    return sum(r-1)-sum(l-1);
  }

  T sum0(int i){
    return sum(i+1);
  }

  void add0(int i,T a){
    add(i+1,a);
  }

  T query0(int l,int r){
    return sum(r)-sum(l);
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#include "../tools/fastio.cpp"
#undef call_from_test

// lower_bound
signed ARC033_C(){
  int q;
  cin>>q;
  BIT<int> bit(2e5);
  while(q--){
    int t,x;
    cin>>t>>x;
    if(t==1) bit.add(x,1);
    if(t==2){
      int k=bit.lower_bound(x);
      bit.add(k,-1);
      cout<<k<<endl;
    }
  }
  return 0;
}
/*
  verified on 2019/11/11
  https://atcoder.jp/contests/arc033/tasks/arc033_3
*/

signed main(){
  ARC033_C();
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename R, size_t N>
struct SquareMatrix{
  typedef array<R, N> arr;
  typedef array<arr, N> mat;
  mat dat;

  SquareMatrix(){
    for(size_t i=0;i<N;i++)
      for(size_t j=0;j<N;j++)
        dat[i][j]=R::add_identity();
  }

  bool operator==(const SquareMatrix& a) const{
    return dat==a.dat;
  }

  size_t size() const{return N;}
  arr& operator[](size_t k){return dat[k];}
  const arr& operator[](size_t k) const {return dat[k];}

  static SquareMatrix add_identity(){return SquareMatrix();}
  static SquareMatrix mul_identity(){
    SquareMatrix res;
    for(size_t i=0;i<N;i++) res[i][i]=R::mul_identity();
    return res;
  }

  SquareMatrix operator*(const SquareMatrix &B) const{
    SquareMatrix res;
    for(size_t i=0;i<N;i++)
      for(size_t j=0;j<N;j++)
        for(size_t k=0;k<N;k++)
          res[i][j]=res[i][j]+(dat[i][k]*B[k][j]);
    return res;
  }

  SquareMatrix operator+(const SquareMatrix &B) const{
    SquareMatrix res;
    for(size_t i=0;i<N;i++)
      for(size_t j=0;j<N;j++)
        res[i][j]=dat[i][j]+B[i][j];
    return res;
  }

  SquareMatrix pow(long long n) const{
    SquareMatrix a=*this,res=mul_identity();
    while(n){
      if(n&1) res=res*a;
      a=a*a;
      n>>=1;
    }
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#include "../tools/fastio.cpp"
#include "../tools/compress.cpp"
#include "../mod/mint.cpp"
#include "../segtree/basic/ushi.cpp"
#undef call_from_test

//INSERT ABOVE HERE
signed YAHOO2019_FINAL_D(){
  using ll = long long;
  using M = Mint<int>;
  using MM = SquareMatrix<M, 2>;

  int n,q;
  cin>>n>>q;
  vector<ll> ts(q),ls(q),rs(q),ps(q);
  for(ll i=0;i<q;i++){
    cin>>ts[i];
    if(ts[i]==1) cin>>ps[i];
    if(ts[i]==2) cin>>ls[i]>>rs[i];
  }
  vector<ll> vs;
  for(ll i=0;i<q;i++){
    if(ts[i]==1){
      vs.emplace_back(ps[i]);
      vs.emplace_back(ps[i]+1);
      vs.emplace_back(ps[i]+2);
      vs.emplace_back(ps[i]+3);
    }
    if(ts[i]==2){
      vs.emplace_back(ls[i]);
      vs.emplace_back(ls[i]+1);
      vs.emplace_back(rs[i]);
      vs.emplace_back(rs[i]+1);
    }
  }
  vs.emplace_back(0);
  vs.emplace_back(n+1);
  vs=compress(vs);
  auto ms=dict(vs);

  MM A;
  A[0][0]=M(1);A[0][1]=M(1);
  A[1][0]=M(1);A[1][1]=M(0);

  vector<MM> vt(vs.size()-1,A);
  for(ll i=0;i+1<(ll)vs.size();i++){
    vt[i]=A.pow(vs[i+1]-vs[i]);
  }

  MM I=MM::mul_identity();
  auto f=[&](MM a,MM b){return b*a;};
  SegmentTree<MM> seg(f,I);
  seg.build(vt);

  vector<int> used(vs.size(),0);
  for(ll i=0;i<q;i++){
    if(ts[i]==1){
      ll k=ms[ps[i]];
      used[k]^=1;
      MM B;
      for(ll j=k;j<=k+2;j++){
        if(used[j]){
          B[0][0]=M(0);B[0][1]=M(0);
          B[1][0]=M(1);B[1][1]=M(0);
        }else{
          B[0][0]=M(!used[j-1]);B[0][1]=M(!used[j-2]);
          B[1][0]=M(1);B[1][1]=M(0);
        }
        seg.set_val(j,B);
      }
    }
    if(ts[i]==2){
      ll l=ms[ls[i]],r=ms[rs[i]];
      if(used[l]){
        cout<<0<<"\n";
        continue;
      }
      auto B=seg.query(l+1,r+1);
      cout<<B[0][0].v<<"\n";
    }
  }
  cout<<flush;
  return 0;
}
/*
  verified on 2019/10/29
  https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_d
*/

signed DDCC2019_FINAL_D(){
  string s;
  cin>>s;

  struct M{
    uint32_t v;
    M(){*this=add_identity();}
    M(uint32_t v):v(v){}
    M operator+(const M &a)const{return M(v+a.v);}
    M operator*(const M &a)const{return M(v*a.v);}
    static M add_identity(){return M(0);}
    static M mul_identity(){return M(1);}
  };

  using SM = SquareMatrix<M, 6>;

  auto f=[](SM a,SM b){return a*b;};
  SM ti=SM::mul_identity();
  SegmentTree<SM> seg(f,ti);
  vector<SM> vt(s.size(),ti);
  for(int i=0;i<(int)s.size();i++){
    if(s[i]=='D') vt[i][0][1]=1;
    if(s[i]=='I') vt[i][1][2]=1;
    if(s[i]=='S') vt[i][2][3]=1;
    if(s[i]=='C') vt[i][3][4]=1;
    if(s[i]=='O') vt[i][4][5]=1;
  }
  seg.build(vt);

  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int l,r;
    cin>>l>>r;
    l--;
    cout<<seg.query(l,r)[0][5].v<<"\n";
  }
  cout<<flush;
  return 0;
}
/*
  verified on 2019/10/29
  https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d
*/

signed main(){
  //YAHOO2019_FINAL_D();
  //DDCC2019_FINAL_D();
  return 0;
}
#endif

#undef call_from_test

//INSERT ABOVE HERE
using ll = long long;

signed YUKI_129(){
  bigint MOD = 1000000000;
  ll n,m;
  cin>>n>>m;
  n/=1000;
  n%=m;
  bigint res(1);
  for(int i=0;i<n;i++){
    res*=m-i;
    res/=i+1;
  }
  cout<<res%MOD<<endl;
  return 0;
}
/*
  verified on 2019/12/17
  https://yukicoder.me/problems/no/129
*/

signed YUKI_303(){
  ll l;
  cin>>l;

  if(l==2){
    cout<<3<<endl;
    cout<<"INF"<<endl;
    return 0;
  }
  cout<<l<<endl;

  using M = SquareMatrix<bigint, 2>;
  M A;
  A[0][0]=1;A[0][1]=1;
  A[1][0]=1;A[1][1]=0;
  if(l&1) cout<<A.pow(l)[1][0]<<endl;
  else{
    auto B=A.pow(l/2);
    auto X=(B*B)[1][0];
    auto Y=B[1][0];
    cout<<X-Y*Y<<endl;
  }
  return 0;
}
/*
  verified on 2019/12/17
  https://yukicoder.me/problems/no/303
*/

const int MAX = 1e5+100;
ll dp[MAX];
pair<bigint, bigint> dfs(int l,int r){
  if(l+1>=r) return make_pair(bigint(dp[l]),bigint(l+1));
  int m=(l+r)>>1;
  auto v=dfs(l,m);
  auto t=dfs(m,r);
  t.first*=v.second;
  t.first+=v.first;
  t.second*=v.second;
  return t;
}

signed YUKI_696(){
  int n;
  cin>>n;
  vector<int> p(n);
  for(int i=0;i<n;i++) cin>>p[i];
  BIT<ll> bit(n+1);
  for(int i=0;i<n;i++) bit.add(p[i],1);
  for(int i=0;i<n;i++){
    dp[n-(i+1)]=bit.sum(p[i]-1);
    bit.add(p[i],-1);
  }
  cout<<bigint(dfs(0,n).first+1)<<endl;
  return 0;
}
/*
  verified on 2019/12/17
  https://yukicoder.me/problems/no/696
*/

signed main(){
  //YUKI_129();
  //YUKI_303();
  YUKI_696();
  return 0;
}
#endif