F. Multiplicative Arrays - 题解

比赛与标签

比赛: Codeforces Round 998 (Div. 3) 标签: combinatorics, dp, number theory, *2200 难度: *2200

题目大意喵~

主人你好呀，这道题是这样的喵~

题目会给我们两个整数 k 和 n。对于从 1 到 k 的每一个整数 x，我们需要找出有多少个不同的整数数组 a，能够同时满足下面这三个条件：

1. 数组 a 的长度 |a| 至少是 1，最多是 n。
2. 数组 a 里的每一个元素 a_i 都在 1 到 k 之间。
3. 数组 a 里所有元素的乘积等于 x。

最后，我们要对每个 x（从 1 到 k）输出它对应的数组数量，并且结果要对 998244353 取模，的说喵~

举个例子，如果 k=2, n=2，对于 x=2，满足条件的数组有 [2], [1, 2], [2, 1]，一共 3 个，呐。

思路分析喵~

这道题看起来有点复杂，n 还那么大，直接去暴力枚举所有数组肯定是不行的啦！所以我们要想个聪明的办法，喵~

首先，我们来观察一下数组中的元素。数字 1 是一个很特别的存在，因为它乘到任何数上都不会改变乘积的值！这给了我们一个很棒的启发：我们可以把问题分成两步来解决！

1. 先只考虑那些大于 1 的数，看看它们能组成哪些乘积。
2. 然后再考虑把任意数量的 1 插到这些数构成的数组里。

第一步：处理大于 1 的数

让我们先专注于构造一个只包含大于 1 的元素的数组，我们叫它 a' 好了。假设这个数组 a' 的长度是 m，并且所有元素的乘积是 x。

怎么计算这种数组 a' 的数量呢？这闻起来就像是动态规划（DP）的味道，喵~

我们可以定义一个 DP 状态：D[x][m] 表示乘积为 x、长度为 m、且所有元素都大于 1 的数组的数量。

• 状态转移: 我们要怎么从已知的状态推导出新的状态呢？可以这样想：一个长度为 m、乘积为 i*j 的数组，可以看作是一个长度为 m-1、乘积为 j 的数组，在末尾追加了一个新元素 i（其中 i > 1）。 所以，我们可以用一种“递推”或者叫“push-style”的 DP：遍历所有已知的 D[j][m-1]，再遍历所有可能的下一个元素 i（从 2 到 k），然后把 D[j][m-1] 的值累加到 D[i*j][m] 上。 转移方程就是：D[i * j][m] = (D[i * j][m] + D[j][m - 1]) % MOD。
• 基础状态: D[1][0] = 1。这代表一个空数组（长度为0），它的乘积是1。这是我们 DP 的起点，喵~

一个关键的发现！m 的最大值会是多少呢？如果一个数组里有 m 个元素，并且每个都至少是 2，那它们的乘积至少是 2^m。因为我们只关心乘积不大于 k 的情况，所以 2^m <= k。这意味着 m <= log₂(k)。 当 k 最大为 10^5 时，log₂(10^5) 大约是 16.6。所以 m 的最大值 M 不会超过 16！哇，这个数字好小呀，这意味着我们的 DP 状态第二维 m 非常小，DP 是完全可行的，的说！

第二步：把 1 加回来

现在我们通过 DP 得到了 D[x][m]，也就是用 m 个大于 1 的数凑成乘积 x 有多少种方案。

接下来，我们要把 1 加回去了。假设我们已经有了一个由 m 个非 1 元素组成的数组（比如 [a'_1, a'_2, ..., a'_m]），它的乘积是 x。我们可以在这个数组的任意位置插入任意多个 1，只要保证最终数组的总长度不超过 n 就行。

假设最终的数组长度是 L（其中 m <= L <= n），那么这个数组里就有 m 个非 1 元素和 L-m 个 1。我们需要把这 m 个非 1 元素安排在 L 个位置上，有多少种方法呢？这其实就是一个组合问题，相当于从 L 个位置中选 m 个位置放非 1 元素，方案数是 C(L, m)。

因为总长度 L 可以是从 m 到 n 的任意值，所以对于一个固定的 m 个非 1 元素的数组，总的方案数就是 sum_{L=m to n} C(L, m)。

这里有一个神奇的组合数学恒等式，叫做“曲棍球棒恒等式”（Hockey-stick identity）： sum_{i=r to n} C(i, r) = C(n+1, r+1) 套用在我们的问题上，就是 sum_{L=m to n} C(L, m) = C(n+1, m+1)。

最终的公式

所以，对于一个给定的 x > 1，它的总方案数就是把所有可能的非 1 元素个数 m 的情况加起来： ans[x] = sum_{m=1 to M} (D[x][m] * C(n+1, m+1))

特殊情况：x = 1 当 x=1 时，数组里只能有 1 这个元素。数组的长度可以是 1, 2, ..., 直到 n。所以可能的数组有 [1], [1,1], [1,1,1], ..., [1...1]（n个1）。总共有 n 种，呐。

计算组合数 C(n, r) 这里的 n 可能会非常大，但 r (也就是 m+1) 会很小（最大也就 17 左右）。所以我们可以用公式 C(n, r) = n * (n-1) * ... * (n-r+1) / r! 来计算。分母 r! 可以预处理出来，除法通过乘以模逆元来实现，的说喵~

总结一下我们的完整流程：

1. 预处理阶乘和阶乘的逆元，为计算组合数做准备。
2. 计算 M = floor(log₂(k))。
3. 使用 DP 计算 D[x][m]，其中 1 <= x <= k, 0 <= m <= M。
4. 单独处理 x=1 的情况，答案是 n。
5. 对于 x 从 2 到 k，使用公式 ans[x] = sum_{m=1 to M} (D[x][m] * C(n+1, m+1)) 计算答案。
6. 输出所有答案，就大功告成啦，喵~！

代码实现

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>

// 使用 GNU G++23 14.2 (64 bit, msys2)
constexpr long long MOD = 998244353;

// 快速幂函数，用来计算 (base^exp) % MOD，喵~
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 利用费马小定理计算模逆元，喵~
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// log2(100000) 大约是 16.6, 所以 M 最大是 16。
// 我们需要计算到 C(n+1, M+1)，所以 r 最大是 M+1=17。
// 阶乘预处理到 17+1=18 就足够啦！
const int MAX_M_PLUS_1 = 18; 
long long fact[MAX_M_PLUS_1];
long long invFact[MAX_M_PLUS_1];

// 预处理阶乘和阶乘的逆元
void precompute_factorials() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < MAX_M_PLUS_1; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]);
    }
}

// 计算组合数 C(n, r) % p，这里 n 很大，r 很小
long long nCr_mod_p(long long n, int r) {
    if (r < 0 || n < r) return 0;
    if (r == 0) return 1;
    // r 不会超过我们预处理的范围
    if (r >= MAX_M_PLUS_1) {
        return 0; // 正常情况下不会到这里
    }
    
    // C(n,r) = n * (n-1) * ... * (n-r+1) / r!
    long long res = invFact[r];
    long long n_mod = n % MOD;
    for (int i = 0; i < r; ++i) {
        res = (res * ((n_mod - i + MOD) % MOD)) % MOD;
    }
    return res;
}

void solve() {
    int k;
    long long n;
    std::cin >> k >> n;

    // 计算非1元素的最大可能数量 M
    int M = 0;
    if (k > 1) {
        M = static_cast<int>(std::floor(std::log2(k)));
    }

    // DP 数组：D[x][m] 表示用 m 个 >1 的数构成乘积 x 的方案数
    std::vector<std::vector<long long>> D(k + 1, std::vector<long long>(M + 1, 0));
    // 基础情况：乘积为1，用0个非1元素，方案数为1（即空数组）
    if (k >= 1) {
        D[1][0] = 1;
    }

    // 开始 DP 啦！这是 "push" 风格的 DP
    for (int m = 1; m <= M; ++m) {
        // i 是新加进来的非1元素 (2 <= i <= k)
        for (int i = 2; i <= k; ++i) {
            // j 是之前 m-1 个元素的乘积
            for (int j = 1; (long long)i * j <= k; ++j) {
                // 从 D[j][m-1] 状态转移到 D[i*j][m]
                if (D[j][m - 1] > 0) {
                    D[i * j][m] = (D[i * j][m] + D[j][m - 1]) % MOD;
                }
            }
        }
    }

    std::vector<long long> ans(k + 1);
    
    // 单独处理 x = 1 的情况
    // 乘积为 1 的数组只能全由 1 构成，长度可以从 1 到 n，所以有 n 种
    if (k >= 1) {
        ans[1] = n % MOD;
    }

    // 计算 x 从 2 到 k 的答案
    for (int x = 2; x <= k; ++x) {
        long long current_ans = 0;
        // 遍历所有可能的非1元素个数 m
        for (int m = 1; m <= M; ++m) {
            if (D[x][m] == 0) continue; // 没有方案，直接跳过
            
            // 我们有 D[x][m] 种方式用 m 个非1元素得到乘积 x
            // 对于每一种，我们可以在总长不超过 n 的数组中插入 1
            // 方案数是 C(n+1, m+1)
            long long combinations = nCr_mod_p(n + 1, m + 1);
            long long term = (D[x][m] * combinations) % MOD;
            current_ans = (current_ans + term) % MOD;
        }
        ans[x] = current_ans;
    }

    // 输出结果，喵~
    for (int i = 1; i <= k; ++i) {
        std::cout << ans[i] << (i == k ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    precompute_factorials(); // 一次性预处理
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

• 时间复杂度: O(Σ k * (log k)²) 的说。 对于每个测试用例，主要耗时在 DP 计算和最终答案的累加。

  1. DP计算部分：有三层循环，m 从 1 到 M (M ≈ log k)，i 从 2 到 k，j 从 1 到 k/i。内两层循环的操作数大约是 Σ(k/i) for i=2 to k，这近似于 k * log k。所以 DP 部分总的是 O(M * k * log k)，也就是 O(k * (log k)²).
  2. 答案计算部分：x 从 2 到 k，m 从 1 到 M。nCr 的计算需要 O(m) = O(M) 的时间。所以这部分是 O(k * M * M) = O(k * (log k)²). 因为题目保证所有测试用例的 k 的总和不超过 10^5，所以总时间复杂度是可以接受的。

• 空间复杂度: O(k * log k) 的说。 主要的内存开销是 DP 数组 D，它的大小是 (k+1) x (M+1)，也就是 O(k * log k)。其他像是 ans 数组是 O(k)，都可以忽略不计啦。

知识点总结

解决这个问题，我们就像一位魔法师一样，巧妙地运用了多种工具，的说喵~

• 主要算法思想: DP + 组合计数。核心思路是“分离变量”，把问题中的 1 和非 1 元素分开处理，大大简化了问题。
• 重要数据结构: 二维 vector (或数组) D[x][m] 用于存储 DP 状态。
• 关键编程技巧:
  • DP 降维思想: 通过 m <= log₂(k) 这个关键观察，将看似无穷的数组长度问题，转化为了一个第二维很小的 DP 问题。
  • “Push” 风格 DP: 代码中实现的 DP 是从当前状态出发，去更新它能到达的未来状态，逻辑清晰。
  • 预处理: 预先计算好阶乘和逆元，避免在循环中重复计算，是优化常用技巧。
• 数学知识:
  • 组合数学: 计算组合数 C(n, r)，特别是当 n 很大 r 很小的情况。
  • 曲棍球棒恒等式: Σ C(i, r) = C(n+1, r+1)，这是将插入 1 的问题从求和化为单次计算的关键！
  • 模运算: 快速幂、费马小定理求逆元，这些都是在模意义下进行计算的基础，喵~
• 注意事项:
  • x=1 是一个特殊情况，需要单独处理。
  • 注意数据范围，n 非常大，不能直接用在循环或数组大小里，但它可以作为组合数公式的参数。k 的范围决定了 DP 表的大小。
  • 所有乘法都要记得及时取模，防止溢出。
• 扩展应用: 这种“分离特殊元素（如 0 或 1）”再用组合数学合并的思想，可以应用在很多计数类问题中。例如，求和为 S 的数组数量，其中元素可以为 0，就可以先计算非 0 元素的方案，再考虑把 0 插进去，喵~

希望这篇题解能帮到你，加油哦，主人！喵~