【hdu 5628】Clarke and math （Dirichlet卷积）

hdu 5628 Clarke and math

题意

题解

代码

代码语言：javascript复制

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;
}

math

0 人点赞