convolution/numbertheoretictransform.cpp

• View this file on GitHub
• Last update: 2021-03-25 09:46:10+09:00

Depends on

• mod/mint.cpp

Required by

• convolution/garner.cpp
• formalpowerseries/998244353.cpp
• mod/factorial.cpp

Verified with

• test/aoj/2560.test.cpp
• test/aoj/2959.test.cpp
• test/aoj/2977.test.cpp
• test/aoj/2985.garner.test.cpp
• test/aoj/3072.test.cpp
• test/aoj/3074.test.cpp
• test/aoj/3084.test.cpp
• test/yosupo/bernoulli_number.test.cpp
• test/yosupo/convolution_mod.test.cpp
• test/yosupo/convolution_mod_1000000007.garner.test.cpp
• test/yosupo/exp_of_formal_power_series.test.cpp
• test/yosupo/inv_of_formal_power_series.test.cpp
• test/yosupo/kth_term_of_linearly_recurrent_sequence.test.cpp
• test/yosupo/log_of_formal_power_series.test.cpp
• test/yosupo/multipoint_evaluation.test.cpp
• test/yosupo/partition_function.test.cpp
• test/yosupo/polynomial_interpolation.test.cpp
• test/yosupo/polynomial_taylor_shift.test.cpp
• test/yosupo/pow_of_formal_power_series.test.cpp
• test/yosupo/sharp_p_subset_sum.test.cpp
• test/yosupo/sqrt_of_formal_power_series.test.cpp
• test/yosupo/stirling_number_of_the_first_kind.test.cpp
• test/yosupo/stirling_number_of_the_second_kind.test.cpp
• test/yukicoder/1504.test.cpp
• test/yukicoder/5633.test.cpp

Code

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

#define call_from_test
#include "../mod/mint.cpp"
#undef call_from_test

#endif
//BEGIN CUT HERE
constexpr int bmds(int x){
  const int v[] = {1012924417, 924844033, 998244353,
                   897581057, 645922817};
  return v[x];
}
constexpr int brts(int x){
  const int v[] = {5, 5, 3, 3, 3};
  return v[x];
}

template<int X>
struct NTT{
  inline static constexpr int md = bmds(X);
  inline static constexpr int rt = brts(X);
  using M = Mint<int, md>;
  vector< vector<M> > rts,rrts;

  void ensure_base(int n){
    if((int)rts.size()>=n) return;
    rts.resize(n);rrts.resize(n);
    for(int i=1;i<n;i<<=1){
      if(!rts[i].empty()) continue;
      M w=M(rt).pow((md-1)/(i<<1));
      M rw=w.inv();
      rts[i].resize(i);rrts[i].resize(i);
      rts[i][0]=M(1);rrts[i][0]=M(1);
      for(int k=1;k<i;k++){
        rts[i][k]=rts[i][k-1]*w;
        rrts[i][k]=rrts[i][k-1]*rw;
      }
    }
  }

  void ntt(vector<M> &as,bool f){
    int n=as.size();
    assert((n&(n-1))==0);
    ensure_base(n);

    for(int i=0,j=1;j+1<n;j++){
      for(int k=n>>1;k>(i^=k);k>>=1);
      if(i>j) swap(as[i],as[j]);
    }

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

    if(f){
      M tmp=M(n).inv();
      for(int i=0;i<n;i++) as[i]*=tmp;
    }
  }

  vector<M> multiply(vector<M> as,vector<M> bs){
    int need=as.size()+bs.size()-1;
    int sz=1;
    while(sz<need) sz<<=1;
    as.resize(sz,M(0));
    bs.resize(sz,M(0));

    ntt(as,0);ntt(bs,0);
    for(int i=0;i<sz;i++) as[i]*=bs[i];
    ntt(as,1);

    as.resize(need);
    return as;
  }

  vector<int> multiply(vector<int> as,vector<int> bs){
    vector<M> am(as.size()),bm(bs.size());
    for(int i=0;i<(int)am.size();i++) am[i]=M(as[i]);
    for(int i=0;i<(int)bm.size();i++) bm[i]=M(bs[i]);
    vector<M> cm=multiply(am,bm);
    vector<int> cs(cm.size());
    for(int i=0;i<(int)cs.size();i++) cs[i]=cm[i].v;
    return cs;
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: convolution/numbertheoretictransform.cpp: line 6: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page