[hdu5628]Clarke and math（dirichlet卷积）

传送门

狄利克雷卷积定义：\[(f*g)(n)=\sum_{d|n}f(d)*g({\frac n d})\]狄利克雷卷积满足交换律：\[f*g=g*f\]结合律：\[(f*g)*h=f*(g*h)\]还有这么几个性质：\[f*\varepsilon=f\] \[f*1=\sum_{d|n}f(d)\]其中\[1(n)=1,\varepsilon(n)=[n=1]\]我们做这个题就是用的上面那条，题目中的式子可以化成这样：\[1^k*f\]然后快速幂就好了。

代码：

#include<bits/stdc++.h>#define ll long longusing namespace std;inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}const int p=1e9+7;int n,k;ll a[100001];void dirichlet(ll *ans,ll *f){memset(a,0,sizeof(a));for(int i=1;i*i<=n;i++){a[i*i]=(a[i*i]+ans[i]*f[i])%p;for(int j=i+1;j*i<=n;j++){a[i*j]=(a[i*j]+ans[i]*f[j])%p;a[i*j]=(a[i*j]+ans[j]*f[i])%p;}}for(int i=1;i<=n;i++)ans[i]=a[i];}ll f[100001],ans[100001],x[100001];void ksm(){int b=k;while(b){if(b&1){dirichlet(ans,x);}dirichlet(x,x);b>>=1;}}void solve(){for(int i=1;i<=n;i++){f[i]=read();x[i]=1;ans[i]=0;}ans[1]=1;ksm();dirichlet(f,ans);for(int i=1;i<n;i++){printf("%lld ",f[i]);}printf("%lld\n",f[n]);}int T;int main(){T=read();while(T--){n=read();k=read();solve();}return 0;}