2019 ICPC EC Final C（狄利克雷卷积）
90nwyn
2020-10-05 23:14:25
[题目链接](https://vjudge.net/problem/Gym-102471C)
------------
$f$在模$mod$下进行$mod$次狄利克雷卷积会得到$[n=1]$
若$f[1]=1$，$f$在模$mod$下进行$k$次狄利克雷卷积得到$g$，那么$g$进行$inv(k)$次狄利克雷卷积将得到$f$
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e5+5,mod=998244353;
int n,k,f[M],g[M],c[M];
int qpow(int a,int b)
{
int y=1;
for(;b;b>>=1,a=(ll)a*a%mod)
if(b&1)y=(ll)y*a%mod;
return y;
}
void conv(int a[],int b[])
{
for(int i=1;i<=n;i++)c[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;i*j<=n;j++)
c[i*j]=(c[i*j]+(ll)a[i]*b[j]%mod)%mod;
for(int i=1;i<=n;i++)a[i]=c[i];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&g[i]);
k=qpow(k,mod-2);
for(f[1]=1;k;k>>=1,conv(g,g))
if(k&1)conv(f,g);
for(int i=1;i<=n;i++)printf("%d ",f[i]);
return 0;
}
```