20191217HNOI 模拟赛 复活石

题目描述：

 

 分析：

我也不知道我在干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?'
':' ');
    }
}