Include

多项式乘法（* *=）

多项式求逆（~  Inv）

多项式除法（/）

多项式取模（%）

多项式对数函数（Ln）

多项式指数函数（Exp）

多项式正弦函数（Cos）

多项式余弦函数（Sin）

 

upda：2019.4.28：

对于任意模数NTT全部适用。

位于：namespace FastFourierTransform

 

开启方法：

 

1.取消注释 using namespace FastFourierTransform;

2.把//dele start here/* 到// delete end here */ 删除或者注释掉。

或者，直接把'/*'敲回车打下去即可。

后面的乘法和求逆都直接调用FastFourierTransform中内置的了。

 

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')using namespace std;typedef long long ll;template
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          il void prt(T a[],int st,int nd){
   for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}//--------------------------------------------------------------------------------------------------------------------//namespace Miracle{const int mod;const int G=3;const int GI=332748118;const int I=86583718;const int iv2=499122177;const double Pi=acos(-1);il int qm(int x,int y){
   int ret=1;while(y){
   if(y&1) ret=(ll)ret*x%mod;x=(ll)x*x%mod;y>>=1;}return ret;}il int ad(int x,int y){
   return x+y>=mod?x+y-mod:x+y;}il int sub(int x,int y){
   return ad(x,mod-y);}il int mul(int x,int y){
   return (ll)x*y%mod;}namespace Polynomial{struct Poly{    vector
          
           f; Poly(){f.clear();} il int &operator[](const int &x){ return f[x];} il const int &operator[](const int &x) const { return f[x];} il void resize(const int &n){f.resize(n);} il int size() const { return f.size();} il void cpy(Poly &b){f.resize(b.size());for(reg i=0;i<(int)f.size();++i)f[i]=b[i];} il void rev(){reverse(f.begin(),f.end());} il void clear(){f.clear();} il void read(const int &n){f.resize(n);for(reg i=0;i
           
            il void rev(T &f){ int lp=f.size(); if(R.size()!=f.size()) { R.resize(f.size()); for(reg i=0;i
            
             >1]>>1)|((i&1)?lp>>1:0); } } for(reg i=0;i
             
              f; Cps(){f.clear();} il cplx &operator[](const int &x){ return f[x];} il const cplx &operator[](const int &x) const { return f[x];} il void resize(const int &n){f.resize(n);} il int size() const { return f.size();} il void cpy(Cps &b){f.resize(b.size());for(reg i=0;i<(int)f.size();++i)f[i]=b[i];} il void rev(){reverse(f.begin(),f.end());} il void clear(){f.clear();} il void out(){ for(reg i=0;i<(int)f.size();++i){ cout<<"("<
              
               <<","<
               
                <<") "; }cout<
                
                 0?W[n/p*(k-l)]:!W[n/p*(k-l)]); f[k+len]=f[k]-tmp; f[k]=f[k]+tmp; } } } if(c==-1){ for(reg i=0;i
                 
                  >15;a[i].y=F[i]&32767; } for(reg i=0;i
                  
                   >15;b[i].y=G[i]&32767; } prework(len); FFT(a,1);FFT(b,1); cplx ka,kb,ba,bb; cplx aaa=cplx(0.5,0),bbb=cplx(0,-0.5),o=cplx(0,1); for(reg i=0;i
                   
                    >1); Poly tmp=h,t; t.resize(n); for(reg i=0;i
                    
                     >1),t; int m=init(n*2); t.resize(m); for(reg i=0;i
                     
                      =1;--i){f[i]=mul(f[i-1],qm(i,mod-2));}f[0]=0;return f;}il Poly Diff(Poly f){ int st=f.size();for(reg i=0;i
                      
                       >1); g.resize(n); g=g*(((Ln(g)*(mod-1))+1)+f); g.resize(n); return g;}il Poly Exp(const Poly &f){ return Exp(f,f.size());}il Poly Cos(const Poly &f){ Poly g=Exp(f*I);return (g+(~g))*iv2;}il Poly Sin(const Poly &f){ Poly g=Exp(f*I);return (g-(~g))*qm(ad(I,I),mod-2);}int main(){ return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle* Date: 2019/4/8 18:57:00*/
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

持（yi）续（ding）更（bu）新（gu）~