多项式快速幂

模板

题意：给多项式 $f(x)$ 和正整数 $k$，求 $f(x{)}^k(\mathrm{mod}{x}^n)$，系数对 $998244353$ 取模。
$k\le 10^{10^5},a_0=1$

前置知识：多项式 $\ln$，多项式 $\exp$。

下面多项式的系数默认对 $998244353$ 取模。

对于求多项式的快速幂，很容易想到整数的快速幂，用类似的方法求出。

但是对于此题，$k\le 10^{10^5}$，太大了，会 TLE。

想到之前学过的多项式 $\ln$，多项式 $\exp$，对原式取 $\ln$ 再取 $\exp$ 可得
$$f(x{)}^k\equiv e^{k\ln f(x)}(\mathrm{mod}{x}^n)$$

这样先做一遍多项式 $\ln$，再做一遍多项式 $\exp$，就可以求出答案了。

但是这里还有个问题，$k$ 那么大，如果对他取模，正确性能否保证呢？如果不行，那怎么办呢？

这里有一个结论：$f(x{)}^p\equiv f(x^p)$

证明：使用数学归纳法。如果 $f(x)$ 只有常数项，显然上式成立。
设 $f(x)$ 的最高次为 $t$，$g(x)$ 是 $f(x)$ 去掉最高次项的多项式，且满足 $g(x{)}^p\equiv g(x^p)$。
则 $f(x)=g(x)+a_t{x}^t$，得出 $f(x{)}^p=(g(x)+a_t{x}^t{)}^p$。
有一个结论 $(a+b{)}^p\equiv a^p+b^p(\mathrm{mod}p)$，证明略。
得到 $f(x{)}^p\equiv g(x{)}^p+a_t^p(x^p{)}^t$
根据费马小定理，$a^p\equiv a(\mathrm{mod}p)$，得 $f(x{)}^p\equiv g(x^p)+a_t(x^p{)}^t$，得证。

对于本题，$n\le 10^5,p=998244353$，所以 n < p n

n<p，那么 $f(x{)}^p\equiv f(x^p)\equiv a_0\equiv 1(\mathrm{mod}{x}^n)$

所以 $f(x{)}^k\equiv f(x{)}^{k\mathrm{mod}p}(\mathrm{mod}{x}^n)$

又可以得到 $f(x{)}^{k\mathrm{mod}p}\equiv e^{(k\mathrm{mod}p)\ln f(x)}(\mathrm{mod}{x}^n)$

这样就可做了。

时间复杂度为 $O(n\log n)$

代码

#include
using namespace std;
typedef long long ll;
const int N=(1<<18)+1;
const ll mod=998244353,g=3,inv2=499122177;
int len=1,n,k;
ll a1[N],w,wn,a[N],ans[N],invans[N],lnans[N],da[N],inva[N],a2[N];
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void change(ll num[])
{
    for(int i=1,j=len/2;i<len-1;i++){
        if(i<j) swap(num[i],num[j]);
        int k=len/2;
        while(j>=k) j-=k,k>>=1;
        if(j<k) j+=k;
    }
}
void ntt(ll num[],int fl)
{
    for(int i=2;i<=len;i<<=1){
        if(fl==1) wn=ksm(g,(mod-1)/i);
        else wn=ksm(g,mod-1-(mod-1)/i);
        for(int j=0;j<len;j+=i){
            w=1;
            for(int k=j;k<j+i/2;k++){
                ll u=w*num[k+i/2]%mod,t=num[k];
                num[k]=(t+u)%mod;
                num[k+i/2]=(t-u+mod)%mod;
                w=w*wn%mod;
            }
        }
    }
    if(fl==-1){
        ll inv=ksm(len,mod-2);
        for(int i=0;i<len;i++) num[i]=num[i]*inv%mod;
    }
}
void getinv(int n,ll a[],ll ans[])
{
	if(n==1){ans[0]=ksm(a[0],mod-2);return;}
	getinv((n+1)/2,a,ans);
	len=1;
	while(len<2*n) len*=2;
	for(int i=0;i<n;i++) a1[i]=a[i];
	for(int i=n;i<len;i++) a1[i]=0;
	change(a1),change(ans);
	ntt(a1,1),ntt(ans,1);
	for(int i=0;i<len;i++) ans[i]=ans[i]*(2-ans[i]*a1[i]%mod+mod)%mod;
	change(ans),ntt(ans,-1);
	for(int i=n;i<len;i++) ans[i]=0;
}
void getln(int n,ll a[],ll ln[])
{
    memset(da,0,sizeof(da));
	for(int i=1;i<n;i++) da[i-1]=a[i]*i%mod;
    da[n-1]=0;
    memset(inva,0,sizeof(inva));
	getinv(n,a,inva);
	len=1;
	while(len<2*n) len*=2;
	change(da),change(inva);
	ntt(da,1),ntt(inva,1);
	for(int i=0;i<len;i++) ln[i]=da[i]*inva[i]%mod;
	change(ln),ntt(ln,-1);
	for(int i=len-1;i>=0;i--) ln[i+1]=ksm(i+1,mod-2)*ln[i]%mod;
    for(int i=n;i<len;i++) ln[i]=0;
	ln[0]=0;
}
void getsqrt(int n,ll a[],ll ans[])
{
    if(n==1){ans[0]=a[0];return;}
    getsqrt((n+1)/2,a,ans);
    len=1;
    while(len<2*n) len*=2;
    memset(invans,0,sizeof(invans));
    getinv(n,ans,invans);
    for(int i=0;i<n;i++) a1[i]=a[i];
    for(int i=n;i<len;i++) a1[i]=0;
    change(a1),change(invans);
    ntt(a1,1),ntt(invans,1);
    for(int i=0;i<len;i++) a1[i]=a1[i]*invans[i]%mod;
    change(a1),ntt(a1,-1);
    for(int i=0;i<n;i++) ans[i]=(a1[i]+ans[i])*inv2%mod;
    for(int i=n;i<len;i++) ans[i]=0;
}
void getexp(int n,ll a[],ll ans[])
{
    if(n==1){ans[0]=1;return;}
    getexp((n+1)/2,a,ans);
    len=1;
    while(len<2*n) len*=2;
    getln(n,ans,lnans);
    for(int i=0;i<n;i++) lnans[i]=(-lnans[i]+a[i]+mod)%mod;
    lnans[0]++;
    change(ans),change(lnans);
    ntt(ans,1),ntt(lnans,1);
    for(int i=0;i<len;i++) ans[i]=ans[i]*lnans[i]%mod;
    change(ans),ntt(ans,-1);
    for(int i=n;i<len;i++) ans[i]=0;
}
void getksm(int n,ll a[],ll k,ll ans[])
{
    memset(a1,0,sizeof(a1));
    getln(n,a,a2);
    for(int i=0;i<n;i++) a2[i]=a2[i]*k%mod;
    getexp(n,a2,ans);
}
ll read()
{
    ll sum=0,c=getchar();
    while(c<48||c>57) c=getchar();
    while(c>=48&&c<=57) sum=(sum*10+c-48)%mod,c=getchar();
    return sum;
}
int main()
{
	scanf("%d",&n);
    k=read();
	for(int i=0;i<n;i++) scanf("%lld",&a[i]),a[i]%=mod;
	getksm(n,a,k,ans);
	for(int i=0;i<n;i++) printf("%lld ",ans[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131