题解：AT_arc202_c [ARC202C] Repunits

· · 题解

首先表示 R_n：R_n = \dfrac {10^n - 1}9。我们将 R_n 同时扩大 9 倍、答案缩小 9 倍不会影响答案。观察到 \gcd(10^a-1,10^b-1) = 10^{\gcd(a, b)-1}，所以考虑把 \rm lcm 写成 \gcd 的形式。容斥原理。

\operatorname{lcm}(S) = \prod_{\varnothing \ne T \subseteq S} \gcd(T)^{(-1)^{|T|+1}}.

注意到这里如果我们计算 \operatorname{lcm}(S,T)，那么容斥系数在 S 和 T 之间按 \gcd-卷积传播。兹定义：假设一个数组 a_X，定义其的值为

v(a_X) = \prod_{X > 0} (10^X-1)^{a_X}.

考虑 T(n) 为数列 f，满足 f_0 = 1, f_n = -1，其余项都为 0；那么我们有：T(a_0), T(a_1), \cdots, T(a_{n - 1}) 的 \gcd-卷积的值为 \mathrm{lcm}(R_{a_0}, R_{a_1}, \cdots, R_{a_{n-1}})^{-1}。

处理 \gcd-卷积，我们一般使用这样一个变换转化为单点乘：

F(n) = \sum_{n \mid k} f(k).

注意到 T(n) 数组的变换 \tilde T 为：

\tilde T_x = 1 - [x \mid n].

因此无论乘多少次，变换后数组一定由 0 和 1 组成，且 0 恰好位于下标至少是一个 a_i 的因数的位置上。

下面是本题最关键的一步：我们能够做到绕开反变换回去，直接根据变换数组 F，求出原数组 f 的值。过程如下：取形式 \log。

\begin{aligned} \log v(f) &= \sum_{X > 0} \log (10^X - 1) f_X \\ &= \sum_{X > 0} \log(10^X - 1) \left( \sum_{X \mid Y} \mu\left(\dfrac YX\right) F_Y \right) \\ &= \sum_{Y \ge 0} F_Y \cdot \left( \sum_{X \mid Y, X > 0} \mu\left(\dfrac YX\right) \log(10^X-1) \right). \end{aligned}

（规定 \mu(0) = -1。）只需计算 \mu 与 \log(10^X-1) 的 Dirichlet 卷积 \rho（备注：\exp \rho(n) 有一个名字为分圆多项式 \Phi_n(10)）。

我们发现，每多一个 0 在位置 d 上，答案就乘以 \Phi_d(10)。这就给出了所求值。

#include <bits/stdc++.h>
using namespace std;

#include "atcoder/all"
using namespace atcoder;

using Z = modint998244353;

int main() {
    int n, V = 0;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x, V = max(V, x + 1);
    vector<vector<int>> dS(V);
    for (int i = 1; i < V; i++)
        for (int j = i; j < V; j += i) dS[j].push_back(i);
    vector<Z> f(V);
    for (int i = 1; i < V; i++) {
        f[i] = (Z(10).pow(i) - 1) / 9;
        for (int d : dS[i])
            if (d != i) f[i] /= f[d];
    }
    Z ans = 1;
    vector<bool> vis(V);
    for (int i : a) {
        for (int d : dS[i])
            if (!vis[d]) vis[d] = 1, ans *= f[d];
        cout << ans.val() << endl;
    }
}