Solution

对于问题\(B(x)=A^k(x) \mod x^n\)

我们有一个既定的式子

\[ B(x)=e^{k\ln(A(x))} \]

如果此时不保证\(a_0=1\)，那么就不能保证\([k\ln(A(x))](0)=0\)，在求exp的时候，就会很麻烦

解决办法是，我们设\(a_tx^t\)是多项式的\(A\)的次数最小的项

那么直接将原来的多项式除去\(a_tx^t\)，最后求完exp后再乘回\(a_t^kx^{tk}\)即可

实践的时候，发现如果直接套用原来的模板，求出来的恰好就是\((\frac{A(x)}{a_tx^t})^k\)

虽然不知道为什么，感觉怎么也证明不出来，貌似是有问题的吧

还是先把原式都除以\(a_tx^t\)再算比较靠谱些

Code 

#include
    
     #define ll long longusing namespace std;#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define reg registerconst int N=1<<18|5,P=998244353,g=3,invg=332748118;inline int read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x*10ll+ch-'0')%P;ch=getchar();}    return x*f;}#define Mul(x,y) (1ll*(x)*(y)%P)#define ri reg int iint _[N],pos[N];int fpow(int x,int m){int r=1;for(;m;m>>=1,x=Mul(x,x))if(m&1)r=Mul(r,x);return r;}void der(int *a,int *b,int n){for(ri=0;i
     
      >1]>>1)|((i&1)*(len>>1));}void NTT(int *a,int n,int type){    register int i,j,k,w,wn,X,Y;    for(i=0;i
      
       0?g:invg,(P-1)/(i<<1));        for(j=0;j
       
        <<1)for(w=1,k=0;k
        
         >1;_I(A,b,t);    static int a[N],len;    for(len=1;len<(n<<1);len<<=1);    memcpy(a,A,sizeof(int[n]));memset(a+n,0,sizeof(int[len-n]));    memset(b+t,0,sizeof(int[len-t]));init(len);    reg int i;NTT(a,len,1);NTT(b,len,1);    for(i=0;i
         
          >1;_e(a,b,t); static int xxx[N]; ln(b,xxx,n);reg int i; for(i=0;i
         
        
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！