题意：求递推式\(f_n = \sum_{i=1}^n a_i f_{n-i}\)，模313

---

多么优秀的模板题

可以用分治fft，也可以多项式求逆

分治fft

注意过程中把r-l+1当做次数界就可以了，因为其中一个向量是[l,mid]，我们只需要[mid+1,r]的结果。

多项式求逆

变成了

\[ A(x) = \frac{f_0}{1-B(x)} \]

的形式

要用拆系数fft，直接把之前的代码复制上就可以啦

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = (1<<18) + 5, mo = 313;const double PI = acos(-1.0);inline int read() {    char c=getchar(); int x=0,f=1;    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}    return x*f;}struct meow{    double x, y;    meow(double a=0, double b=0):x(a), y(b){}};meow operator +(meow a, meow b) {return meow(a.x+b.x, a.y+b.y);}meow operator -(meow a, meow b) {return meow(a.x-b.x, a.y-b.y);}meow operator *(meow a, meow b) {return meow(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);}meow conj(meow a) {return meow(a.x, -a.y);}typedef meow cd;namespace fft {    int maxlen = 1<<17, rev[N];    cd omega[N], omegaInv[N];    void init() {        for(int i=0; i
         
          >1]>>1) | ((i&1)<<(k-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int l=2; l<=n; l<<=1) { int m = l>>1; for(cd *p = a; p != a+n; p += l) for(int k=0; k
          
           >1; cdq(l, mid); int n = 1; while(n < r-l+1) n <<= 1; for(int i=0; i
          
         
        
       
      
     
    

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = (1<<18) + 5, mo = 313, P = 313;const double PI = acos(-1.0);inline int read() {    char c=getchar(); int x=0,f=1;    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}    return x*f;}inline int Pow(int a, int b) {    int ans = 1;    for(; b; b>>=1, a=a*a%P)        if(b&1) ans=ans*a%P;    return ans;}struct meow{    double x, y;    meow(double a=0, double b=0):x(a), y(b){}};meow operator +(meow a, meow b) {return meow(a.x+b.x, a.y+b.y);}meow operator -(meow a, meow b) {return meow(a.x-b.x, a.y-b.y);}meow operator *(meow a, meow b) {return meow(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);}meow conj(meow a) {return meow(a.x, -a.y);}typedef meow cd;namespace fft {    int maxlen = 1<<18, rev[N];    cd omega[N], omegaInv[N];    void init() {        for(int i=0; i
         
          >1]>>1) | ((i&1)<<(k-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int l=2; l<=n; l<<=1) { int m = l>>1; for(cd *p = a; p != a+n; p += l) for(int k=0; k
          
           >1); int n = l<<1; for(int i=0; i
           
            >15), b[i] = cd(y[i]&32767); for(int i=l; i
            
             >15), b[i] = cd(x[i]&32767), c[i] = cd(z[i]>>15), d[i] = cd(z[i]&32767); for(int i=l; i