hdu 5628 Clarke and math

题意

Given f(i),1≤i≤n, calculate

\(\displaystyle g(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_k \mid i_{k-1}} f(i_k) \text{ mod } 1000000007 \quad (1 \le i \le n)\)

题解

Dirichlet convolution -wiki

别人的题解

恒等函数1(n)=1。

那么\(\sum_{i_k \mid i_{k-1}} f(i_k)\) 就是\(f(i_k)\)与\(1(\frac {i_{k-1}} {i_k})\) 的狄利克雷卷积

然后再和$ 1(\frac {i_{k-2}} {i_{k-1}})$卷积。。。

再用的狄利克雷卷积满足交换律，所以就是 \(g(i)=\sum_{j|i}f(j)1^k\)

代码

const int N=201000;

int n,k;

ll tmp[N],x[N],f[N],ans[N];

void dirichlet(ll *ans, ll *x){

	mem(tmp,0);

	rep(i,1,sqrt(n)+1){

		tmp[i*i]+=ans[i]*x[i]%mod;

		rep(j,i+1,n/i+1){

			tmp[i*j]+=ans[i]*x[j]%mod;

			tmp[i*j]+=ans[j]*x[i]%mod;

		}

	}

	rep(i,1,n+1)

		ans[i]=tmp[i]%mod;

}

void qpow(){

	for(;k;k>>=1,dirichlet(x, x))

		if(k&1) dirichlet(ans, x);

}

int main() {

	int t;

	sf(t);

	while(t--){

		sf(n);sf(k);

		rep(i,1,n+1){

			sfl(f[i]);

			ans[i]=0;

			x[i]=1;

		}

		ans[1]=1;

		qpow();

		dirichlet(ans, f);

		rep(i,1,n+1)printf("%lld%c",ans[i],i==n?'\n':' ');

	}

	return 0;

}