1. 题目

传送门=￣ω￣=

题意：

给定序列 $f$，设：

$$\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)$$

给定 $n,k,1 \le n,k \le 10^5$，输出 $g(i),1 \le i \le n$

有多组数据，数据组数小于等于 5 组

2. 题解

考场上遇到了这题然后别人都会就我不会。

我太蒻了

前两天 boshi 还刚发了一篇关于狄利克雷卷积的博客

可惜我没看

我就从来没考过做过的题

我太蒻了

好吧我们来看看这题怎么做

首先对于 $k=1$的情况：

$$g(i)=\sum_{i_1\mid i}f(i_1)$$

有点像狄利克雷卷积不是吗？

我们再设这个函数：

$$f'(i)=1$$

那么：
$$g(i)=\sum_{d\mid i}f(d)\cdot f'(\frac{n}{d})$$

也就是说：
$$g=f*f’$$

这里 “*” 表示狄利克雷卷积

那如果 $k=2$呢？

不难发现，我们把 $k=1$时得到的 $g$看做 $f$，再做一次 $g=f*f’$就得到了 $k=2$时的 $g$

也就是说：

$$g=f * f’ * f’ * f’…$$（乘了 $k$次）

因为狄利克雷卷积符合交换律与结合律，所以式子可以写成 $g=f*f’^k$，其中 $f’^k$我们可以用快速幂来计算。

总复杂度就是 $O(nlog_2nlog_2k)$的了（因为计算一次狄利克雷卷积复杂度是 $O(nlog_2n)$的）

（但其实我的代码里还有一个分解因数，复杂度是 $O(n\sqrt{n})$的）

具体看代码里面的注释吧

代码：

#include <bits/stdc++.h>

#define NS (100005)
#define MOD (1000000007)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int T, n, k;

LL tmp[NS];

vector<int> dn[NS];//存约数的动态长数组

struct Func
{
    LL v[NS];
    LL& operator [] (const int a) {return v[a];}
    void operator *= (Func oth)//计算狄利克雷卷积
    {
        memset(tmp, 0, sizeof(tmp));
        for (int i = 1; i <= n; i += 1)
            for (vector<int>::iterator it = dn[i].begin(); it != dn[i].end(); it++)
                tmp[i] = (tmp[i] + v[*it] * oth[i / *it] % MOD) % MOD;
        memmove(v, tmp, sizeof(v));
    }
}g, f, p;

void qpow(Func a, int b)//快速幂
{
    memset(p.v, 0, sizeof(p.v)), p[1] = 1;//先把 p 设为单位元，和普通快速幂里的 1 是一个意思
    while (b)
    {
        if (b & 1) p *= a;
        a *= a, b >>= 1;
    }
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), IN(k);
        for (int i = 1; i <= n; i += 1)//O(n sqrt(n)) 计算每个数字的约数
        {
            dn[i].clear();
            for (int j = 1; j * j <= i; j += 1)
                if (i % j == 0)
                {
                    dn[i].push_back(j);
                    if (i / j != j) dn[i].push_back(i / j);
                }
        }
        for (int i = 1; i <= n; i += 1) IN(g[i]), f[i] = 1;//这里 f 就是文中的 f'
        qpow(f, k), g *= p;
        for (int i = 1; i < n; i += 1) printf("%lld ", g[i]);//这里还 PE 了一次=。=
        printf("%lld\n", g[n]);
    }
    return 0;
}