HDU-5628-Clarke-and-math-狄利克雷卷积 HDU-5628-Clarke-and-math-狄利克雷卷

分析：这个题目要学会数论上面的一个知识点：狄利克雷卷积。
主要要知道:

(f?g)=∑d|nf(d)g(nd)
f?(g?h)=(f?g)?h
f?(g+h)=f?g+f?h
f?g=g?f

【HDU-5628-Clarke-and-math-狄利克雷卷积】这道题就变成了这个 f?1k 时候用一次快速幂，可以 nlog(n) 复杂度解决
代码部分：

#include using namespace std; typedef long long LL; #define FOR(i,x,y)for(int i = x; i < y; ++ i) #define IFOR(i,x,y)for(int i = x; i > y; -- i)const int maxn = 100010; const int Mod = 1000000007; int n,k; LL f[maxn],g[maxn],h[maxn],e[maxn]; void solve(){ while(k){ if(k % 2){ FOR(i,1,n+1)e[i] = 0; for(int i = 1; i*i <= n; ++ i) for(int j = i; j*i <= n; ++ j) if(j == i)e[i*j] += h[i]*g[i]%Mod,e[i*j] %= Mod; elsee[i*j] += (h[i]*g[j]%Mod+h[j]*g[i]%Mod)%Mod,e[i*j] %= Mod; FOR(i,1,n+1)h[i] = e[i]; } FOR(i,1,n+1)e[i] = 0; for(int i = 1; i*i <= n; ++ i) for(int j = i; j*i <= n; ++ j) if(j == i)e[i*j] += g[i]*g[i]%Mod,e[i*j] %= Mod; elsee[i*j] += (g[i]*g[j]%Mod+g[j]*g[i]%Mod)%Mod,e[i*j] %= Mod; FOR(i,1,n+1)g[i] = e[i]; k >>= 1; } FOR(i,1,n+1)e[i] = 0; for(int i = 1; i*i <= n; ++ i) for(int j = i; j*i <= n; ++ j) if(j == i)e[i*j] += f[i]*h[j]%Mod,e[i*j] %= Mod; elsee[i*j] += (f[i]*h[j]%Mod+h[i]*f[j]%Mod)%Mod,e[i*j] %= Mod; FOR(i,1,n+1)h[i] = e[i]; }int main(){ //freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&k); FOR(i,1,n+1)scanf("%I64d",&f[i]),g[i] = 1,h[i] = 0; h[1] = 1; solve(); printf("%I64d",h[1]); FOR(i,2,n+1)printf(" %I64d",h[i]); printf("\n"); } return 0; }