题意：
给定长度为n的g函数值g(1)，g(2)，…g(n)， 已知
g
=
f
∗
f
.
.
.
.
.
.
∗
f
=
f
k
g=f*f......*f=f^k
g=f∗f......∗f=fk，求f(1)，f(2)，…f(n)。 式子中的星号表示迪利克雷卷积。 答案对998244353取模。
数据范围：n<=1e5，k<998244353
解法：
g
=
f
k
g=f^k
g=fk
g
i
n
v
[
k
]
=
(
f
k
)
i
n
v
[
k
]
g^{inv[k]}=(f^k)^{inv[k]}
ginv[k]=(fk)inv[k]
g
i
n
v
[
k
]
=
f
k
∗
i
n
v
[
k
]
=
f
g^{inv[k]}=f^{k*inv[k]}=f
ginv[k]=fk∗inv[k]=f
直
接
计
算
g
i
n
v
[
k
]
即
可
，
用
快
速
幂
算
直接计算g^{inv[k]}即可，用快速幂算
直接计算ginv[k]即可，用快速幂算
迪
利
克
雷
卷
积
O
(
n
∗
l
o
g
)
，
快
速
幂
O
(
l
o
g
)
，
总
复
杂
度
O
(
n
∗
l
o
g
∗
l
o
g
)
迪利克雷卷积O(n*log)，快速幂O(log)，总复杂度O(n*log*log)
迪利克雷卷积O(n∗log)，快速幂O(log)，总复杂度O(n∗log∗log)
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
#define ll long long
#define PI pair<int,int>
const int maxm
=1e5+5;
const int mod
=998244353;
int n
,k
;
struct Node
{
int a
[maxm
];
Node
operator*(const Node
& x
)const{
Node ans
;
memset(ans
.a
,0,sizeof ans
.a
);
for(int i
=1;i
<=n
;i
++){
for(int j
=i
;j
<=n
;j
+=i
){
ans
.a
[j
]=(ans
.a
[j
]+a
[i
]*x
.a
[j
/i
]%mod
)%mod
;
}
}
return ans
;
}
};
Node a
,ans
;
int ppow(int a
,int b
,int mod
){
int ans
=1%mod
;a
%=mod
;
while(b
){
if(b
&1)ans
=ans
*a
%mod
;
a
=a
*a
%mod
;
b
>>=1;
}
return ans
;
}
signed main(){
cin
>>n
>>k
;
for(int i
=1;i
<=n
;i
++){
cin
>>a
.a
[i
];
}
ans
.a
[1]=1;
int b
=ppow(k
,mod
-2,mod
);
while(b
){
if(b
&1)ans
=ans
*a
;
a
=a
*a
;
b
>>=1;
}
for(int i
=1;i
<=n
;i
++){
cout
<<ans
.a
[i
]<<' ';
}
return 0;
}
