题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=5628
题目大意：
输入 \(n\) 和 \(k\)，对于每个 \(i(1 \le i \le n)\)，求
\[f(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}
\]
答案对 \(10^9 + 7\) 取模。
解题思路：
数论函数 \(f(n)\) 和 \(g(n)\) 的 狄利克雷卷积 \(f \ast g\) 定义为
\[(f \ast g)(n) = \sum_{d \mid n} f(d) g(\frac{n}{d}) = \sum_{de = n} f(d) g(e)
\]
定义一个单位函数 \(I(n) = 1\)。有
\[f(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_{k-1} \mid i_{k-2}} \left( \sum_{i_k \mid i_{k-1}} f_{i_k} I(\frac{i_{k-1}}{i_k}) \right)
\]
\[= \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_{k-1} \mid i_{k-2}} (f \ast I)(i_{k-1})
\]
\[= \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_{k-3} \mid i_{k-2}} \sum_{i_{k-1} \mid i_{k-2}} (f \ast I)(i_{k-1})
\]
\[= \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_{k-3} \mid i_{k-2}} \left( \sum_{i_{k-1} \mid i_{k-2}} (f \ast I)(i_{k-1}) I(\frac{i_{k-2}}{i_{k-1}}) \right)
\]
\[= \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_{k-3} \mid i_{k-2}} \left( \sum_{i_{k-1} \mid i_{k-2}} (f \ast I \ast I)(i_{k-2}) \right)
\]
\[= ...
\]
\[= (f \ast I \ast \cdot \ast I)(i)
\]
\[= (f \ast I^k)(i)
\]
其中，\(I^k\) 表示 \(k\) 个 \(I\) 做狄利克雷卷积的结果。\(\rightarrow\) 我们可以用 快速幂 的方式优化这个卷积。
然后再拿 \(f\) 和 \(I^k\) 做一次卷积就可以了。
示例程序：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long mod = 1e9 + 7;int T, n, k;vector<ll> dc(vector<ll> a, vector<ll> b, int n) {vector<ll> c(n+1, 0);for (int i = 1; i <= n; i++) {for (int j = 1; i * j <= n; j++) {(c[i * j] += a[i] * b[j]) %= mod;}}return c;
}vector<ll> dpow(vector<ll> a, int b, int n) {vector<ll> res(n+1, 0);res[1] = 1;for (; b; b >>= 1, a = dc(a, a, n)) {if (b & 1)res = dc(res, a, n);}return res;
}int main() {scanf("%d", &T);while (T--) {scanf("%d%d", &n, &k);vector<ll> f(n+1, 0);for (int i = 1; i <= n; i++)scanf("%lld", &f[i]);vector<ll> I(n+1, 1);I[0] = 0;f = dc(f, dpow(I, k, n), n);for (int i = 1; i <= n; i++) {if (i > 1) putchar(' ');printf("%lld", f[i]);}putchar('\n');}return 0;
}