题目描述：
分析：
我也不知道我在干sm，但就是没写出来2333
枚举 i 的每个质因子 j ，复杂度为n^(3/2)
为什么我会认为是n^2啊2333
然后考虑 f ( j )对g ( i )做了多少贡献
这个值当然与x=i / j有关
对每个x的质因子分开考虑
那么设某个因子P的指数为A
那么对于中途sigma的某一位的值Ik，他们的因子P的指数为Ak
那么为了满足整除性，我们知道Ak是单调不上升的
那么就可以用组合数算了。。。
构造长度为K的不超过Ak的不下降序列的方案数相当于将Ak个有标号小球放入K个编了号的箱子中，箱子可空
差分一下就看出来了2333
那么方案数就为C(K+Ak-1,Ak)
对于x的总方案，就是所有质因子方案数相乘，我们设为W(x)
所以g ( i ) = sigma( j | i ) f ( j ) * W ( i / j )
其中W是可以O( n^(3/2) )预处理的
所以总复杂度为O( n^(3/2) )
此外题解说有一个神仙卷积法，考场上想过但是为什么不继续想啊
太菜了，复习复习。。。
( f * g )(n) = sigma ( j | i ) f ( j ) *g ( i / j )
我***考试中这式子都写在纸上了怎么还不会啊2333好菜啊2333
答案就是( f * I ) (n) ^ k，其中函数I中所有值都为1
快速卷卷起来不就好啦。。。
/*龙门粗口*/
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<vector> #define maxn 200005 #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; inline int getint() { int num=0,flag=1;char c; while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)flag=-1; while(c>=‘0‘&&c<=‘9‘)num=num*10+c-48,c=getchar(); return num*flag; } int n,K; long long f[maxn]; long long g[maxn]; int pri[maxn],cnt,np[maxn]; long long fac[maxn],inv[maxn]; long long W[maxn]; inline long long C(int p,int q) {return fac[p]*inv[q]%MOD*inv[p-q]%MOD;} inline void init() { for(int i=2;i<maxn/100;i++) { if(!np[i])pri[++cnt]=i; for(int j=1;j<=cnt&&i*pri[j]<maxn/100;j++) { np[i*pri[j]]=1; if(i%pri[j]==0)break; } } fac[0]=fac[1]=inv[0]=inv[1]=1; for(int i=2;i<maxn;i++)fac[i]=fac[i-1]*i%MOD; for(int i=2;i<maxn;i++)inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD; for(int i=2;i<maxn;i++)inv[i]=inv[i]*inv[i-1]%MOD; } int main() { int T=getint(); init(); while(T--) { memset(g,0,sizeof g); n=getint(),K=getint(); for(int i=1;i<=n;i++) { int tmp=i;W[i]=1; for(int j=1;j<=cnt&&pri[j]<=tmp;j++) if(tmp%pri[j]==0) { int cur=0; while(tmp%pri[j]==0)tmp/=pri[j],cur++; (W[i]*=C(K+cur-1,cur))%=MOD; } if(tmp>1)(W[i]*=K)%=MOD; } for(int i=1;i<=n;i++)f[i]=getint(); for(int i=1;i<=n;i++)for(int j=1;j*j<=i;j++) if(i%j==0) { (g[i]+=f[j]*W[i/j])%=MOD; if(j*j!=i)(g[i]+=f[i/j]*W[j])%=MOD; } for(int i=1;i<=n;i++)printf("%lld%c",g[i],i==n?‘\n‘:‘ ‘); } }
原文：https://www.cnblogs.com/Darknesses/p/12056747.html
