题解：AT_abc461_f [ABC461F] Total Product is N

· · 题解

说在前面

卡线过的。

还是挺简单的吧。

前置芝士：分解质因数、01 背包。

题目分析

先考虑一个东西，假设这个东西是一个大小为 k 的无序集合，那么你把它转变为有序数列，就是 k! 个有序数列。

所以总答案显然就是所有合法无序子集的元素和 \times k! 之和。

观察：N \le 10 ^ {10}，有两个显然的性质：

这启示我们枚举所有约数并使用 01 背包 DP。

那么我们应该怎么设计这个东西呢？应该维护两个东西：

那么我们的转移，就是相当于做一个 01 背包一样，这里使用刷表法，ni 表示下一步乘积做的映射，d 表示新加入的数字：

\begin{cases} f _ {i+1, ni} \gets f _ {i+1, ni} + f _ {i, j} \\ g _ {i +1, ni} \gets g _ {i+1,ni} + g _ {i, j} + d \cdot f _ {i,j} \end{cases}

设 N 的映射为 p，那么最终的答案就是这个式子：

ans = \sum _ {i = 1} ^ {max\_i} g _ {i, p} \cdot i!

完整代码

:::success[AC 代码]

#include <bits/stdc++.h>

#define int long long

using namespace std;

namespace zcq_qwq {
    const int N = 50 + 5, mod = 998244353, M = 3000;

    int p[N], e[N], div[M], fact[N], f[N][M], g[N][M];

    int cd, cf;

    unordered_map<int, int> id;

    void BB(int n) { // 分解质因数
        cf = 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                int cnt = 0;
                while(n % i == 0) {
                    cnt++;
                    n /= i;
                }
                p[cf] = i;
                e[cf] = cnt;
                cf++;
            }
        }
        if (n > 1) {
            p[cf] = n;
            e[cf] = 1;
            cf++;
        }
    }

    void BB2() { // 计算约数，存进 div
        cd = 1;
        div[0] = 1;
        for (int i = 0; i < cf; i++) {
            int sz = cd;
            int pe = 1;
            for (int j = 0; j < e[i]; j++) {
                pe *= p[i];
                for (int k = 0; k < sz; k++) {
                    div[cd++] = div[k] * pe;
                }
            }
        }
    }

    void main() {
        int x;
        cin >> x;
        BB(x);
        BB2();
        for (int i = 0; i < cd; i++) id[div[i]] = i; // 作映射
        fact[0] = 1; // 初始化
        for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % mod;
        f[0][id[1]] = 1;
        for (int i = 0; i < cd; i++) { // 01 背包
            int d = div[i];
            int d_mod = d % mod;
            for (int k = N - 2; k >= 0; k--) {
                for (int j = 0; j < cd; j++) {
                    if (f[k][j] == 0) continue;
                    int m = div[j];
                    if (m > x / d) continue;
                    int nm = m * d;
                    if (id.find(nm) == id.end()) continue;
                    int ni = id[nm]; // 肥肠简单的转移
                    f[k + 1][ni] = (f[k + 1][ni] + f[k][j]) % mod;
                    int add = (g[k][j] + d_mod * f[k][j] % mod) % mod;
                    g[k + 1][ni] = (g[k + 1][ni] + add) % mod;
                }
            }
        }
        int ans = 0; 
        for (int k = 1; k < N; k++) { // 算答案
            ans = (ans + g[k][id[x]] * fact[k] % mod) % mod;
        }
        cout << ans << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    zcq_qwq::main();
    return 0;
}

:::

说在后面

若代码、思路讲解有误，欢迎提出！