[Solution] ARC116C Multiple Sequences

· · 题解

计数题。这里主要详解利用 隔板法 计数的推导过程。

Solution

若不断地枚举倍数以转移 dp 方程，时间复杂度为 O(nm)。

考虑将枚举倍数转为枚举最后一个数 x，继而转为枚举其质因子，分配质因子的指数使数组单调上升至 x。如图：

由于 M\le 2\times 10^5，每个数至多有 6 个质因数。

设 x 的质因子 a 指数为 m，将其分配至前 n-1 个数可以抽象为：将 m 个数分配给 n 个抽屉，抽屉可以留空，求方案数。

隔板法模型：方程 \sum_{i=1}^n x_i=m 的正整数解数量为 C_{m-1}^{n-1}。

考虑将题目再做转换：计算方程 \sum_{i=1}^n x_i=m 的 非负整数解 数量。如果可以将非负整数解转为正整数解处理，即可使用隔板法：

\sum_{i=1}^nx_i=m \sum_{i=1}^n(x_i+1)=n+m

此时 x+1>0，考虑设 y_i=x_i+1。将 y_i 带入方程，可以将题目转换为：计算 \sum_{i=1}^ny_i=n+m 的正整数解数量。根据隔板法，方案数为 C_{n+m-1}^{n-1}。

枚举时统计答案即可。

时间复杂度 O(n\sqrt n)，不过显然跑不满，瓶颈在于枚举质因子。

Code

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

namespace Cherry {
    #define Add(x, y) (x + y < mod ? x + y : x + y - mod)
    const int N = 4e5 + 25;
    const long long mod = 998244353;
    int n, m, ans;
    int fac[N], inv[N];

    long long ksm(long long x, long long k) {
        int res = 1;
        while (k) {
            if (k & 1) res = 1ll * res * x % mod;
            x = 1ll * x * x % mod;
            k >>= 1;
        }
        return res;
    }
    void init(int n) {
        fac[0] = 1;
        for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[n] = ksm(fac[n], mod - 2);
        for (int i = n - 1; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
    }
    int C(int n, int m) {
        if (n < m || m < 0) return 0;
        return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
    }

    int main() {
        scanf("%d%d", &n, &m), init(400020);
        for (int i = 1; i <= m; i++) {
            int x = i, sum = 1;
            for (int j = 2; j * j <= x; j++) {
                int cnt = 0;
                while (x % j == 0) x /= j, cnt++;
                sum = 1ll * sum * C(n + cnt - 1, n - 1) % mod; // 隔板法计算答案
            }
            if(x > 1) sum = 1ll * sum * n % mod; // 注意 x 本身为质数时需要额外计算
            ans = Add(ans, sum);
        }
        printf("%d", ans);

        return 0;
    }
}

int main() {
    Cherry::main();

    return 0;
}

Bonus！

CF2206I Growth Factor

可以尝试思考加强版 ( /•ω•\ )！题解：[Solution] CF2206I Growth Factor。