传送门
题解：
我记得 SCOI2019 考完之后我就口胡过这个东西，当时D1T3 超矩形。。。
考虑 Dirichlet 生成函数：
F
(
x
)
=
∑
i
≥
1
f
i
i
x
F(x)=\sum_{i\geq 1}\frac{f_i}{i^x}
F
(
x
)
=
∑
i
≥
1
i
x
f
i
。
考虑 Dirichlet 卷积：
(
f
∗
g
)
(
n
)
=
∑
d
∣
n
f
(
d
)
g
(
n
d
)
(f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})
(
f
∗
g
)
(
n
)
=
∑
d
∣
n
f
(
d
)
g
(
d
n
)
，不难发现 Dirichlet 卷积的 Dirichlet 生成函数就是原 Dirichlet 生成函数的卷积。
所以我们现在只需要考虑生成函数的开根和求幂即可，支持一下
ln
\ln
ln
和
exp
\exp
exp
就行了，我们只需要明白
ln
\ln
ln
怎么做，
exp
\exp
exp
直接就是
ln
\ln
ln
的逆运算。
按照套路
ln
F
(
x
)
=
∫
F
′
(
x
)
F
(
x
)
\ln F(x)=\int \frac{F'(x)}{F(x)}
ln
F
(
x
)
=
∫
F
(
x
)
F
′
(
x
)
，求逆没什么好讲的，直接搞就行了，求导会发现这个玩意 ：
(
f
i
i
x
)
′
=
−
f
i
i
x
ln
i
(\frac{f_i}{i^x})’=-\frac{f_i}{i^x}\ln i
(
i
x
f
i
)
′
=
−
i
x
f
i
ln
i
这个
ln
i
\ln i
ln
i
有点难搞，不过我们知道外层有个求不定积分最后会把
ln
i
\ln i
ln
i
搞掉，我们需要维护的只有比值，就是说我们需要构造函数
c
(
n
)
c(n)
c
(
n
)
，使其满足
c
(
1
)
=
0
,
c
(
i
j
)
=
c
(
i
)
+
c
(
j
)
c(1)=0,c(ij)=c(i)+c(j)
c
(
1
)
=
0
,
c
(
i
j
)
=
c
(
i
)
+
c
(
j
)
。定义
c
(
i
)
c(i)
c
(
i
)
为
i
i
i
的所有质因子指数之和即可。
代码：
#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const
namespace IO{
inline char gc(){
static cs int Rlen=1<<22|1;static char buf[Rlen],*p1,*p2;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}template<typename T>T get_integer(){
char c;bool f=false;while(!isdigit(c=gc()))f=c=='-';T x=c^48;
while(isdigit(c=gc()))x=((x+(x<<2))<<1)+(c^48);return f?-x:x;
}inline int gi(){return get_integer<int>();}
char obuf[(int)(1e7+7)],*oh=obuf,ch[23];
template<typename T>void print(T a,char c){
if(a<0)*oh++='-',a=-a;int tl=0;
do ch[++tl]=a%10;while(a/=10);
while(tl)*oh++=ch[tl--]^48;*oh++=c;
}struct obuf_flusher{~obuf_flusher(){fwrite(obuf,1,oh-obuf,stdout);}}Flusher;
}using IO::gi;
using IO::print;
using std::cerr;
using std::cout;
cs int mod=998244353;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
inline void Inc(int &a,int b){a+=b-mod,a+=a>>31&mod;}
inline void Dec(int &a,int b){a-=b,a+=a>>31&mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int po(int a,int b){int r=1;for(;b;b>>=1,Mul(a,a))if(b&1)Mul(r,a);return r;}
inline void ex_gcd(int a,int b,int &x,int &y){
if(!b){x=1,y=0;return;}ex_gcd(b,a%b,y,x);y-=a/b*x;
}inline int Inv(int a){static int x,y;ex_gcd(mod,a,y,x);return x+(x>>31&mod);}
cs int N=1e6+7;
int p[N],pc;
bool mrk[N];
int c[N];
void sieves(int n){
for(int re i=2;i<=n;++i){
if(!mrk[i])p[++pc]=i,c[i]=1;
for(int re j=1;i*p[j]<=n;++j){
mrk[i*p[j]]=true;
c[i*p[j]]=c[i]+1;
if(i%p[j]==0)break;
}
}
}
int inv[100];
void Ln(int *f,int *t,int n){
for(int re i=1;i<=n;++i)
t[i]=mul(f[i],c[i]);
for(int re i=1;i<=n;++i)if(t[i])
for(int re j=2;i*j<=n;++j)
Dec(t[i*j],mul(f[j],t[i]));
for(int re i=1;i<=n;++i)
Mul(t[i],inv[c[i]]);
}
void Exp(int *f,int *t,int n){
for(int re i=1;i<=n;++i)
t[i]=i==1,Mul(f[i],c[i]);
for(int re i=1;i<=n;++i)if(t[i]){
Mul(t[i],inv[c[i]]);
for(int re j=2;i*j<=n;++j)
Inc(t[i*j],mul(t[i],f[j]));
}
}
void Root(int *f,int n,int k){
static int g[N];
Ln(f,g,n);k=Inv(k);
for(int re i=1;i<=n;++i)
Mul(g[i],k);
Exp(g,f,n);
}
int n,k;
int f[N];
void Main(){
n=gi(),k=gi();inv[0]=inv[1]=1;
for(int re i=2;i<100;++i)
inv[i]=mul(inv[mod%i],mod-mod/i);
for(int re i=1;i<=n;++i)f[i]=gi();
sieves(n);Root(f,n,k);
for(int re i=1;i<=n;++i)
print(f[i],' ');
}
inline void file(){
#ifdef zxyoi
freopen("dirichlet.in","r",stdin);
#endif
}signed main(){file();Main();return 0;}