AtCoder Beginner Contest 461

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

void solve() {
    int x, y;
    cin >> x >> y;
    if (x <= y) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

void solve() {
    int x, y;
    cin >> x >> y;
    if (x <= y) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B – The Honest Woodcutters

题意

给出两个数组 $a， b$ ，第 $i$ 个樵夫说它拥有第 $a_i$ 把斧头，仙女知道第 $i$ 把斧头是樵夫 $b_i$ 的，问是否每个樵夫说的都是实话

思路

与 $（i, a_i）$ 相对应的是 $(b_i, i)$ ， $i = b_i, a_i = i$

樵夫	1	2	3	…	n
斧头	$a_1$	$a_2$	$a_3$	…	$a_n$
斧头	1	2	3	…	n
樵夫	$b_1$	$b_2$	$b_3$	…	$b_n$

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n +1), b(n +1);

    set<pair<int, int>> st;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        st.insert({a[i], i});
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        if (!st.count({i, b[i]})) {
            cout << "No" << endl;
            return ;
        }
    }
    cout << "Yes" << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n +1), b(n +1);

    set<pair<int, int>> st;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        st.insert({a[i], i});
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        if (!st.count({i, b[i]})) {
            cout << "No" << endl;
            return ;
        }
    }
    cout << "Yes" << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C – Variety

题意

有 $N$ 颗宝石。第 $i$ 颗宝石的颜色（用整数表示）是 $C _ i$ ，它的价值是 $V _ i$ 。

从这些 $N$ 颗宝石中选择 $K$ 颗宝石。这里，所选的宝石必须至少有 $M$ 种不同的颜色。

求所选宝石的最大可能总值。

思路

将宝石根据价值从大到小排序。两次遍历，第一次，只要碰见新的颜色，则加入到答案中。第二次遍历，只要碰见之前没选的就加入到答案中。整个过程保证选取个数小于等于 $K$

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

struct Node {
    LL c, v;
    bool operator<(const Node &t) const {
        if (v != t.v) return v > t.v;
        return c < t.c;
    }
};

void solve() {
    LL n, k, m;
    cin >> n >> k >> m;

    vector<Node> node;

    vector<LL> vis(n +1, 0);
    for (LL i = 1; i <= n; ++i) {
        LL c, v;
        cin >> c >> v;
        node.push_back({c, v});
    }

    sort(node.begin(), node.end());

    LL cnt =0, sm = 0;
    set<LL> st;
    for (LL i = 0; i < n; ++i) {
        auto [c, v] = node[i];
        if (cnt < m && !st.count(c)) {
            st.insert(c);
            vis[i] = 1;
            sm += v;
            ++cnt;
        }
    }

    for (LL i = 0; i < n; ++i) {
        auto [c, v] = node[i];
        if (cnt < k && !vis[i]) {
            sm += v;
            ++cnt;
        }
    }

    cout << sm << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;

struct Node {
    LL c, v;
    bool operator<(const Node &t) const {
        if (v != t.v) return v > t.v;
        return c < t.c;
    }
};

void solve() {
    LL n, k, m;
    cin >> n >> k >> m;

    vector<Node> node;

    vector<LL> vis(n +1, 0);
    for (LL i = 1; i <= n; ++i) {
        LL c, v;
        cin >> c >> v;
        node.push_back({c, v});
    }

    sort(node.begin(), node.end());

    LL cnt =0, sm = 0;
    set<LL> st;
    for (LL i = 0; i < n; ++i) {
        auto [c, v] = node[i];
        if (cnt < m && !st.count(c)) {
            st.insert(c);
            vis[i] = 1;
            sm += v;
            ++cnt;
        }
    }

    for (LL i = 0; i < n; ++i) {
        auto [c, v] = node[i];
        if (cnt < k && !vis[i]) {
            sm += v;
            ++cnt;
        }
    }

    cout << sm << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D – Count Subgrid Sum = K

题意

有一个 $H×W$ 网格，每个单元格都包含一个整数 0 或 1 。给一个整数 $k$

求，满足矩形中 $1$ 的个数刚好等于 $k$ 的矩形个数

思路

${\color{yellow}二维前缀和，双指针}$

我最开始，朴素的想法自然是暴力，因为他的数量级真的很小，才 500，但是如果纯暴力的话，枚举左上角的点，然后枚举宽和高，时间复杂度是 $O(n^4)$ ，过不了，但是可以优化到 $O（n^3）$ ，左上角的点是必须枚举的，然后枚举宽，发现一个单调性，由于 $k$ 是定值，宽越大，高就越小，所以，用双指针或者二分都可以，但我推荐用双指针，少一个 $log$ 的复杂度

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> s(n +2, vector<int>(m +2));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            s[i][j] = c - '0';
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            s[i][j] += s[i - 1][j];
        }
    }

    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            s[i][j] += s[i][j - 1];
        }
    }


    auto area = [&](int x1, int y1, int x2, int y2) {
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    };

    int ans = 0;
    for (int x1 = 1; x1 <= n; ++x1) {
        for (int y1 = 1; y1 <= m; ++y1) {
            int y2 = m, pre = -1;
            for (int x2 = x1; x2 <= n; ++x2) {
                if (x2 > x1 && area(x2 - 1, y1, x2, y2) == 0 && pre !=-1) {
                    ans += pre;
                    continue;
                }
                while (y2 >= y1 && area(x1, y1, x2, y2) > k) {
                    --y2;
                }
                int yy2 = y2;
                while (yy2 >= y1 && area(x1, y1, x2, yy2) == k) {
                    ++ans;
                    --yy2;
                }
                pre = y2 - yy2;
            }
        }
    }
    cout << ans << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> s(n +2, vector<int>(m +2));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            s[i][j] = c - '0';
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            s[i][j] += s[i - 1][j];
        }
    }

    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            s[i][j] += s[i][j - 1];
        }
    }


    auto area = [&](int x1, int y1, int x2, int y2) {
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    };

    int ans = 0;
    for (int x1 = 1; x1 <= n; ++x1) {
        for (int y1 = 1; y1 <= m; ++y1) {
            int y2 = m, pre = -1;
            for (int x2 = x1; x2 <= n; ++x2) {
                if (x2 > x1 && area(x2 - 1, y1, x2, y2) == 0 && pre !=-1) {
                    ans += pre;
                    continue;
                }
                while (y2 >= y1 && area(x1, y1, x2, y2) > k) {
                    --y2;
                }
                int yy2 = y2;
                while (yy2 >= y1 && area(x1, y1, x2, yy2) == k) {
                    ++ans;
                    --yy2;
                }
                pre = y2 - yy2;
            }
        }
    }
    cout << ans << endl;
}

signed main() {
#ifdef JiuQi
    freopen("test_1.in", "r", stdin);
    freopen("test_1.out", "w", stdout);
#endif // JiuQi

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E – E-liter

题意

给你一个 $n \times n$ 的网格，有 $m$ 次询问，若询问为 $1 \:\ R$ ，则第 $R$ 行都涂成黑色，若询问为 $2 \;\ C$ ，则第 $C$ 列都涂成白色，最开始所有格子都是白色。问，每次询问后，黑色格子的数量

思路

${\color{yellow}树状数组}$

最开始的总量为零，去找当前询问与上一次的变化量，维护每一次的总量

若当前询问为 $1 \;\ R$ ，则增加的黑色格子数为上一次的 $1 \;\ R$ 与这一次的 $1 \;\ R$ 之间的 $2 \;\ C$ 的数量（去重），于是，问题就转换成了求满足条件的区间和，用树状数组维护即可

$tr / tc$ : 维护在该询问前，该行列的修改最后一次出现的时间

$bit\_r / bit\_c$ : 维护每次询问的时间戳，将时间戳作为“键”。有多少行/列最后一次操作在这个时间

对于第 $i$ 次查询，

若询问为 $1 \;\ R$ ，查询 $[tr_R, i]$ 之间有多少个 $bit\_c_j$

若询问为 $2 \;\ C$ ，查询 $[tr_C + 1, i]$ 之间有多少个 $bit\_r_j$

我靠，真的只有自己写了才知道，这里面还有恶心人的细节：

对于 $1 \;\ R$ ，可以直接查询 $[tr_R, i]$ ，但是对于 $2 \;\ C$ ，查询的范围是 $[tr_C + 1, i]$ ，因为若 $tr_C = 0$ ，则会查询到若干个还没有变成黑色的行，能够减去的前提是之前一定先变成过黑色。第二个易错点是， $[tr_C +1,i]$ 查询出来的答案可能为负，若第一次的询问是 $2 \;\ 1$ ，则查询范围是 $[1, 1]$ ， $sum(1) – sum(0) = -n$ ，所以，需要与 $0$ 取上界

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define lowbit(x) (x & (-x))

struct BIT {
    int n;
    vector<int> tr;

    void init(int n_) {
        n = n_;
        tr.assign(n + 1, 0);
    }

    void add(int x, int k) {
        ++x;
        for (; x <= n; x += lowbit(x)) {
            tr[x] += k;
        }
    }

    int sum(int x) {
        ++x;
        int ans = 0;
        for (; x; x -= lowbit(x)) {
            ans += tr[x];
        }
        return ans;
    }

    int query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    BIT bit_r, bit_c;
    bit_r.init(q + 10);
    bit_c.init(q + 10);

    vector<int> tr(n + 5, 0), tc(n + 5, 0);
    bit_r.add(0, n);
    bit_c.add(0, n);

    int cur = 0;
    for (int i = 1; i <= q; ++i) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            // int delta = n - bit_c.sum(tr[x] - 1);
            int delta = bit_c.query(tr[x], i);
            cur += delta;
            bit_r.add(tr[x], -1);
            tr[x] = i;
            bit_r.add(tr[x], 1);
        }
        else {
            // int delta = n - bit_r.sum(tc[x]);
            int delta = max(bit_r.query(tc[x] + 1, i), 0LL);
            cur -= delta;
            bit_c.add(tc[x], -1);
            tc[x] = i;
            bit_c.add(tc[x], 1);
        }
        cout << cur << endl;
    } 
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define lowbit(x) (x & (-x))

struct BIT {
    int n;
    vector<int> tr;

    void init(int n_) {
        n = n_;
        tr.assign(n + 1, 0);
    }

    void add(int x, int k) {
        ++x;
        for (; x <= n; x += lowbit(x)) {
            tr[x] += k;
        }
    }

    int sum(int x) {
        ++x;
        int ans = 0;
        for (; x; x -= lowbit(x)) {
            ans += tr[x];
        }
        return ans;
    }

    int query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    BIT bit_r, bit_c;
    bit_r.init(q + 10);
    bit_c.init(q + 10);

    vector<int> tr(n + 5, 0), tc(n + 5, 0);
    bit_r.add(0, n);
    bit_c.add(0, n);

    int cur = 0;
    for (int i = 1; i <= q; ++i) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            // int delta = n - bit_c.sum(tr[x] - 1);
            int delta = bit_c.query(tr[x], i);
            cur += delta;
            bit_r.add(tr[x], -1);
            tr[x] = i;
            bit_r.add(tr[x], 1);
        }
        else {
            // int delta = n - bit_r.sum(tc[x]);
            int delta = max(bit_r.query(tc[x] + 1, i), 0LL);
            cur -= delta;
            bit_c.add(tc[x], -1);
            tc[x] = i;
            bit_c.add(tc[x], 1);
        }
        cout << cur << endl;
    } 
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F – Total Product is N

题意

给出一个数 $n$ ，有一个非空的序列 $a$ 满足以下条件：

$a_1 \.\ a_2 \.\ a_3 \ … a_m = n$
$a_1 \neq a_2 \neq a_3 … \neq a_n$

问，所有满足条件的序列之和

思路

${\color{yellow}动态规划}$

先分解 $n$ ，找到 $n$ 的因数，构成 $a$ 的的元素只可能在 $n$ 的因数中出现，数量级就可以从 $1e10$ 下降到 $1e5$ 。我们想要知道一种和对应的分解方案数，用方案数去乘以和即可。

由于位置的不同对答案也有影响，所以需要保存选取的个数，最后乘以个数的阶乘。由于要求序列和，所以要保存当前的和是多少，根据条件最后的乘积为 $n$ ，所以得保留中途过程中选取的因数的乘积。状态就定义出来了 $dp[k][j][sm]$ 表示讨论了前 $i$ 个因数，选取 $k$ 个，乘积为 $a_j$ ，和为 $sm$ 的方案数，但是，由于和是在太大，三个维度加起来没法存，所以分解一下 -> 把 $sm$ 单拎出来， $cnt[k][j]$ 表示选取 $k$ 个，乘积为 $a_j$ 的方案数， $sm[k][j]$ 表示选取 $k$ 个，乘积为 $a_j$ 的方案之和（不考虑顺序）

将 $n$ 进行因数分解，从小到大讨论他的因数，当讨论到 $x$ 时：

若 $a_j \not\equiv 0 \;(mod \;\ x)$ ，则跳过，否则，进行下面讨论

若要选取 $x$ : $cnt[k][j] \to cnt[k-1][p]$ ( $p$ 是 $\frac{a_j}{x}$ 这个数的位置）， $sum[k][j] \to sm[k – 1][p] + cnt[k-1][p] \.\ x$

若不选取 $x$ : 则直接继承上一次状态，不变

代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

const int MOD = 998244353;

void solve()
{
    int N;
    cin >> N;

    vector<int> a;

    a.push_back(0);
    for (int i = 1; i * i <= N; ++i)
    {
        if (N % i == 0)
        {
            a.push_back(i);

            if (i * i != N)
            {
                a.push_back(N / i);
            }
        }
    }

    sort(a.begin(), a.end());

    int m = a.size() - 1;

    const int K = 14;

    vector<int> fac(K + 1, 0);
    fac[0] = 1;
    for (int i = 1; i <= K; ++i)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }

    vector<vector<int>> cnt(K + 1, vector<int>(m + 1, 0));
    vector<vector<int>> sum(K + 1, vector<int>(m + 1, 0));

    cnt[0][1] = 1;

    int ans = 0;
    for (int i = 1; i <= m; ++i)
    {
        int x = a[i];
        for (int k = K; k >= 1; --k)
        {
            for (int j = 1; j <= m; ++j)
            {
                if (a[j] % x != 0)
                    continue;
                int y = a[j] / x;
                y = lower_bound(a.begin() + 1, a.end(), y) - a.begin();

                cnt[k][j] = (cnt[k][j] + cnt[k - 1][y]) % MOD;

                sum[k][j] = ((sum[k - 1][y] + cnt[k - 1][y] * x) % MOD + sum[k][j]) % MOD;
            }
        }
    }

    for (int i = 1; i <= K; ++i)
    {
        ans = (ans + sum[i][m] * fac[i] % MOD) % MOD;
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

const int MOD = 998244353;

void solve()
{
    int N;
    cin >> N;

    vector<int> a;

    a.push_back(0);
    for (int i = 1; i * i <= N; ++i)
    {
        if (N % i == 0)
        {
            a.push_back(i);

            if (i * i != N)
            {
                a.push_back(N / i);
            }
        }
    }

    sort(a.begin(), a.end());

    int m = a.size() - 1;

    const int K = 14;

    vector<int> fac(K + 1, 0);
    fac[0] = 1;
    for (int i = 1; i <= K; ++i)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }

    vector<vector<int>> cnt(K + 1, vector<int>(m + 1, 0));
    vector<vector<int>> sum(K + 1, vector<int>(m + 1, 0));

    cnt[0][1] = 1;

    int ans = 0;
    for (int i = 1; i <= m; ++i)
    {
        int x = a[i];
        for (int k = K; k >= 1; --k)
        {
            for (int j = 1; j <= m; ++j)
            {
                if (a[j] % x != 0)
                    continue;
                int y = a[j] / x;
                y = lower_bound(a.begin() + 1, a.end(), y) - a.begin();

                cnt[k][j] = (cnt[k][j] + cnt[k - 1][y]) % MOD;

                sum[k][j] = ((sum[k - 1][y] + cnt[k - 1][y] * x) % MOD + sum[k][j]) % MOD;
            }
        }
    }

    for (int i = 1; i <= K; ++i)
    {
        ans = (ans + sum[i][m] * fac[i] % MOD) % MOD;
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

错误代码

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int MOD = 998244353;

int dp[15][15][200010]; // 选前 k 个，乘积为 a[j]，总和为 sm 的方案数

void solve() {
    int n;
    cin >> n;

    vector<int> a(1);

    for (int i = 1; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            a.push_back(i);

            if (i * i != n)
                a.push_back(n / i);
        }
    }

    sort(a.begin(), a.end());

    int m = a.size() - 1;
    int K = 14;

    dp[0][1][0] = 1;

    for (int i = 1; i <= m; ++i) {
        int x = a[i];
        for (int k = K; k >= 1; --k) {
            for (int j = 1; j <= m; ++j) {
                for (int sm = x; sm <= 2e5; ++sm)
                {
                    if (a[j] % x != 0)
                        continue;
                    int y = a[j] / x;
                    int p = lower_bound(a.begin() + 1, a.end(), y) - a.begin();
                    dp[k][j][sm] = (dp[k][j][sm] + dp[k - 1][p][sm - x]) % MOD;
                }
            }
        }
    }

    vector<int> fac(K + 1, 0);

    fac[0] = 1;
    for (int i = 1; i <= K; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }

    int ans = 0;
    for (int i = 1; i <= K; ++i)
    {
        for (int sm = 1; sm <= 2e5; ++sm)
        {
            ans = (ans + sm * dp[i][m][sm] % MOD * fac[i] % MOD) % MOD;
        }
    }

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

// 你爱它的清新又厌它的寡淡，喜恶同因，它只是水而已
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int MOD = 998244353;

int dp[15][15][200010]; // 选前 k 个，乘积为 a[j]，总和为 sm 的方案数

void solve() {
    int n;
    cin >> n;

    vector<int> a(1);

    for (int i = 1; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            a.push_back(i);

            if (i * i != n)
                a.push_back(n / i);
        }
    }

    sort(a.begin(), a.end());

    int m = a.size() - 1;
    int K = 14;

    dp[0][1][0] = 1;

    for (int i = 1; i <= m; ++i) {
        int x = a[i];
        for (int k = K; k >= 1; --k) {
            for (int j = 1; j <= m; ++j) {
                for (int sm = x; sm <= 2e5; ++sm)
                {
                    if (a[j] % x != 0)
                        continue;
                    int y = a[j] / x;
                    int p = lower_bound(a.begin() + 1, a.end(), y) - a.begin();
                    dp[k][j][sm] = (dp[k][j][sm] + dp[k - 1][p][sm - x]) % MOD;
                }
            }
        }
    }

    vector<int> fac(K + 1, 0);

    fac[0] = 1;
    for (int i = 1; i <= K; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }

    int ans = 0;
    for (int i = 1; i <= K; ++i)
    {
        for (int sm = 1; sm <= 2e5; ++sm)
        {
            ans = (ans + sm * dp[i][m][sm] % MOD * fac[i] % MOD) % MOD;
        }
    }

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

别人代码（DFS）

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

const int N = 3e5 + 5;
const ll mod = 998244353;

ll fac[N], n, ans;

void dfs(ll now, ll la, ll len, ll sum)
{
    ans = (ans + fac[len] * (now + sum) % mod) % mod;
    for (ll i = la + 1; i * i < now; ++i)
    {
        if (now % i == 0)
        {
            dfs(now / i, i, len + 1, sum + i);
        }
    }
}

void solve()
{
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= N - 5; ++i)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    dfs(n, 0, 1, 0);
    cout << ans << '\n';
}

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

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

const int N = 3e5 + 5;
const ll mod = 998244353;

ll fac[N], n, ans;

void dfs(ll now, ll la, ll len, ll sum)
{
    ans = (ans + fac[len] * (now + sum) % mod) % mod;
    for (ll i = la + 1; i * i < now; ++i)
    {
        if (now % i == 0)
        {
            dfs(now / i, i, len + 1, sum + i);
        }
    }
}

void solve()
{
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= N - 5; ++i)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    dfs(n, 0, 1, 0);
    cout << ans << '\n';
}

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

“啊，英雄岁月，地久天长……”

— 老猪 · 紫川

一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

A – Armor

题意

思路

代码