懒得放传送【大雾

有趣的一道题

前几天刚好听到Creed_神犇讲到相乘转原根变成卷积的形式

看到这道题当然就会做了啊w

对于m很小 我们暴力找原根 如果你不会找原根的话 出门左转百度qwq

找到原根以后所有数转成原根的幂次然后卷积就吼了啊

多项式卡速米 由于是循环卷积所以每一次还要转回系数相加再转回来

所以是不优美的O(nlg^2n) =v=

代码在这里。

//Love and Freedom.#include
    
     #include
     
      #include
      
       #include
       
        #define inf 20021225#define ll long long#define wph 1004535809ll#define mxn 810000using namespace std;int ksm(int bs,int mi,int mdn){    int ans=1;    while(mi)    {        if(mi&1)	ans=(ll)ans*bs%mdn;        bs=(ll)bs*bs%mdn; mi>>=1;    }    return ans;}int n,m,x,s;int G,rev[mxn<<1];int id[mxn];void find_G(){    for(int i=2;i<=m;i++)    {        memset(id,0,sizeof(id));        int tmp=1,j;        for(j=0;j
        
         i)        swap(a[rev[i]],a[i]);    for(int k=2,mid=1;k<=n;k<<=1,mid<<=1)    {        int Wn=ksm(3,(wph-1)/k,wph);        if(f)	Wn=ksm(Wn,wph-2,wph);        for(int i=0,w=1;i
         
          >1]>>1)|((i&1)<<(l-1)); return lim;}void poly_ksm(int *ans,int *bs,int n,int mi){ //for(int i=0;i
          
           >=1; } NTT(ans,lim,1); //for(int i=0;i