NekoNowcoder

Appearance

DisgustingRelationship - 题解 ​

标签与难度 ​

标签: 数论, 组合数学, 整数划分, 动态规划, 生成函数 难度: 2300

题目大意喵~ ​

哈喵~ 各位算法大师们好呀！这道题有点复杂，让我来给大家梳理一下吧，喵~

题目是这样子的：有 nn 个小可爱，他们之间存在一种叫做“恋爱关系”的东西。每个人都只喜欢唯一的一个人，而且不会有两个人喜欢同一个人。这种关系其实就是一个 11 到 nn 的排列（Permutation），比如说 [3, 1, 2] 就表示 1号喜欢3号，2号喜欢1号，3号喜欢2号。

这种关系可以看成一个图，每个人是一个点，如果 A 喜欢 B，就有一条从 A 到 B 的有向边。因为是排列，所以每个点的入度和出度都正好是1。这样的图一定会分解成若干个不相交的环，我们称之为“k-love polygon”（kk元恋爱环），其实就是长度为 kk 的环啦。

一个“恋爱关系”的类型（type）由它包含的各种长度环的数量决定。比如，对于 n=5n=5 的一种关系，它可能包含一个3元环和一个2元环，那么它的类型就是 (a_1=0, a_2=1, a_3=1, a_4=0, a_5=0)。当然，要满足所有环的总人数是 nn，也就是 ∑k=1nk⋅ak=n\sum_{k=1}^{n} k \cdot a_k = n。这正好是整数 nn 的一个整数划分（Integer Partition）！

对于每一种类型 (a_1, ..., a_n)，我们可以计算出有多少种具体的排列能构成这种类型，记这个数量为 f(a1,...,an)f(a_1, ..., a_n)。

现在，Avery 有一个讨厌的规矩：如果一个类型的排列数量 f(a1,...,an)f(a_1, ..., a_n) 能够被他最喜欢的数字 PP 整除，那么他就觉得这种类型是“恶心的”（disgusting）。

我们的任务是，对于给定的 nn 和 PP，找出有多少种不同类型的恋爱关系是不恶心的。也就是说，我们要计算有多少种整数划分 (a_1, ..., a_n) 满足 ∑k⋅ak=n\sum k \cdot a_k = n，并且对应的排列数 f(a1,...,an)f(a_1, ..., a_n) 不能被 PP 整除。

解题思路分析 ​

喵呼~ 这道题的题面看起来好吓人，又是排列又是环的，但核心其实是一个非常有趣的数论计数问题！

首先，我们得知道那个神奇的函数 f(a1,…,an)f(a_1, \dots, a_n) 是什么。在组合数学中，一个具有 aka_k 个长度为 kk 的环 (k=1,…,nk=1, \dots, n) 的 nn 元排列的数量，其计算公式是：

f(a1,…,an)=n!∏k=1n(kak⋅ak!)f(a_1, \dots, a_n) = \frac{n!}{\prod_{k=1}^{n} (k^{a_k} \cdot a_k!)}

我们要找的就是满足 ∑k⋅ak=n\sum k \cdot a_k = n 且 f(a1,…,an)≢0(modP)f(a_1, \dots, a_n) \not\equiv 0 \pmod P 的整数划分 (a1,…,an)(a_1, \dots, a_n) 的数量。

直接去分析这个分数的整除性实在是太复杂了，会让我的脑袋变成一团乱麻的！(>ω<) 幸运的是，数学家们已经为我们铺好了路。对于这类问题，有一个非常深刻和优美的结论。这里我们假设题目中的 PP 是一个素数（在竞赛中，涉及整除性的模数 PP 通常都是素数）。

✨ 神奇的数论定理 ✨ ​

设 UP(n)U_P(n) 为我们要求解的答案，即满足条件的整数划分数量。一个重要的数论定理告诉我们：

UP(n)=p(n(modP))⋅∏i=1k(ni+1)U_P(n) = p(n \pmod P) \cdot \prod_{i=1}^{k} (n_i + 1)

这里的 p(r)p(r) 是整数划分函数，表示将正整数 rr 写成一个或多个正整数之和的方案数（不考虑顺序）。而 nin_i 是 nn 在 PP 进制下的各位数字。具体来说，如果 nn 的 PP 进制表示为 n=nkPk+⋯+n1P+n0n = n_k P^k + \dots + n_1 P + n_0 (其中 0≤ni<P0 \le n_i < P)，那么公式就是这样的。

但是，参考代码实现的是一个稍微不同的版本，它将 nn 分为 n=qP+rn = qP + r 两部分，其中 r=n(modP)r = n \pmod P 是余数，q=⌊n/P⌋q = \lfloor n/P \rfloor 是商。答案可以表示为：

UP(n)=p(r)⋅HP(q)U_P(n) = p(r) \cdot H_P(q)

其中 HP(q)H_P(q) 是一个与商 qq 有关的函数，它的计算方式是：将 qq 写成 PP 进制 q=qmPm+⋯+q1P+q0q = q_m P^m + \dots + q_1 P + q_0，然后 HP(q)=∏j=0m(qj+1)H_P(q) = \prod_{j=0}^{m} (q_j + 1)。

这个公式把一个复杂的问题分解成了两个独立的部分，是不是很神奇呀？

  1. 计算 p(n(modP))p(n \pmod P): 我们需要计算余数 rr 的整数划分数。
  2. 计算 ∏(qj+1)\prod (q_j+1): 我们需要对商 qq 进行 PP 进制分解，然后计算一个简单的乘积。

下面我们就来看看这两个部分要怎么实现吧！

1. 计算整数划分数 p(k)p(k) ​

计算 p(k)p(k) 的经典方法是使用动态规划，而其递推关系由大名鼎鼎的欧拉五边形数定理（Euler's Pentagonal Number Theorem）给出。该定理指出：

p(k)=∑j=1∞(−1)j−1(p(k−gj)+p(k−hj))p(k) = \sum_{j=1}^{\infty} (-1)^{j-1} \left( p(k - g_j) + p(k - h_j) \right)

其中 gj=j(3j−1)2g_j = \frac{j(3j-1)}{2} 和 hj=j(3j+1)2h_j = \frac{j(3j+1)}{2} 是广义五边形数。 展开来看就是：

p(k)=p(k−1)+p(k−2)−p(k−5)−p(k−7)+p(k−12)+…p(k) = p(k-1) + p(k-2) - p(k-5) - p(k-7) + p(k-12) + \dots

递推项的符号规律是 +, +, -, -, +, +, ...

因为题目中 PP 的最大值是 10510^5，所以我们需要预处理出 p(0)p(0) 到 p(100004)p(100004) 的所有值。p(0)p(0) 我们定义为 11。这个预处理的时间复杂度大约是 O(NN)O(N \sqrt{N})，其中 NN 是预处理的范围，完全可以接受。

2. 计算乘积部分 ​

这部分就简单多啦。我们拿到商 q=⌊n/P⌋q = \lfloor n/P \rfloor，然后就像做短除法求进制转换一样，不断地取 q(modP)q \pmod P 得到当前最低位的数字，然后令 q=⌊q/P⌋q = \lfloor q/P \rfloor。

举个栗子，喵~ 比如要计算 H3(35)H_3(35)：

  1. q=35,P=3q=35, P=3。
  2. 当前位是 35(mod3)=235 \pmod 3 = 2。乘积是 (2+1)=3(2+1)=3。qq 变为 ⌊35/3⌋=11\lfloor 35/3 \rfloor = 11。
  3. 当前位是 11(mod3)=211 \pmod 3 = 2。乘积是 3×(2+1)=93 \times (2+1) = 9。qq 变为 ⌊11/3⌋=3\lfloor 11/3 \rfloor = 3。
  4. 当前位是 3(mod3)=03 \pmod 3 = 0。乘积是 9×(0+1)=99 \times (0+1) = 9。qq 变为 ⌊3/3⌋=1\lfloor 3/3 \rfloor = 1。
  5. 当前位是 1(mod3)=11 \pmod 3 = 1。乘积是 9×(1+1)=189 \times (1+1) = 18。qq 变为 ⌊1/3⌋=0\lfloor 1/3 \rfloor = 0。
  6. qq 变成 0，循环结束。最终结果是 18。

总结一下步骤 ​

  1. 预处理: 使用五边形数定理，计算并存储 p(k)p(k) 对于 k=0k=0 到 100004100004 的值。所有计算都在模 109+710^9+7 下进行。
  2. 处理查询: 对于每组输入的 nn 和 PP： a. 计算余数 r=n(modP)r = n \pmod P 和商 q=⌊n/P⌋q = \lfloor n/P \rfloor。 b. 从预处理的表格中查到 p(r)p(r)。 c. 写一个循环来计算 HP(q)=∏(qj+1)H_P(q) = \prod (q_j+1)。 d. 最终答案就是 p(r)×HP(q)(mod109+7)p(r) \times H_P(q) \pmod{10^9+7}。

这样一来，问题就迎刃而解啦！是不是感觉清晰多了呢？喵~

代码实现 ​

这是我根据上面的思路，精心重构的一份代码，希望能帮助你更好地理解呐！

cpp
#include <iostream>
#include <vector>
#include <numeric>

// 使用 long long 防止 n 溢出
using ll = long long;

// 定义模数
const int MOD = 1e9 + 7;
// 定义预处理的上限，根据题目 P 的范围设定
const int MAX_P = 100005;

// 用于存储预计算的整数划分数 p(k)
std::vector<int> partition_counts;

// 预处理整数划分数的函数
void precompute_partitions() {
    partition_counts.resize(MAX_P);
    
    // p(0) = 1 是基本情况
    partition_counts[0] = 1;

    for (int k = 1; k < MAX_P; ++k) {
        // 使用五边形数定理计算 p(k)
        for (int j = 1; ; ++j) {
            // 计算两个广义五边形数
            ll pentagonal1 = (ll)j * (3 * j - 1) / 2;
            ll pentagonal2 = (ll)j * (3 * j + 1) / 2;

            bool stop = true; // 标记是否可以提前结束循环

            if (k >= pentagonal1) {
                stop = false;
                if (j % 2 == 1) { // 符号是 +
                    partition_counts[k] = (partition_counts[k] + partition_counts[k - pentagonal1]) % MOD;
                } else { // 符号是 -
                    partition_counts[k] = (partition_counts[k] - partition_counts[k - pentagonal1] + MOD) % MOD;
                }
            }

            if (k >= pentagonal2) {
                stop = false;
                if (j % 2 == 1) { // 符号是 +
                    partition_counts[k] = (partition_counts[k] + partition_counts[k - pentagonal2]) % MOD;
                } else { // 符号是 -
                    partition_counts[k] = (partition_counts[k] - partition_counts[k - pentagonal2] + MOD) % MOD;
                }
            }

            if (stop) {
                break;
            }
        }
    }
}

void solve(int case_num) {
    ll n;
    int p;
    std::cin >> n >> p;

    // 1. 计算余数和商
    ll remainder = n % p;
    ll quotient = n / p;

    // 2. 从预处理表中获取 p(remainder)
    ll result = partition_counts[remainder];

    // 3. 计算商的乘积部分 H_p(quotient)
    ll product_part = 1;
    if (quotient == 0) {
        product_part = 1;
    } else {
        while (quotient > 0) {
            ll digit = quotient % p;
            product_part = (product_part * (digit + 1)) % MOD;
            quotient /= p;
        }
    }

    // 4. 合并结果
    result = (result * product_part) % MOD;

    std::cout << "Case #" << case_num << ": " << result << std::endl;
}

int main() {
    // 加速输入输出
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 进行一次全局预处理
    precompute_partitions();

    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
    }

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(MAX_PMAX_P+T⋅log⁡Pn)O(MAX\_P \sqrt{MAX\_P} + T \cdot \log_P n)

    • 预处理 precompute_partitions 的时间复杂度是 O(MAX_PMAX_P)O(MAX\_P \sqrt{MAX\_P})，因为对于每个 kk，内部循环的次数大约是 k\sqrt{k}。这部分在所有测试用例前只执行一次。
    • 每个测试用例 solve 的时间复杂度主要由计算商的乘积部分决定，这个循环的次数是 q=⌊n/P⌋q = \lfloor n/P \rfloor 在 PP 进制下的位数，即 O(log⁡Pq)O(\log_P q) 或 O(log⁡Pn)O(\log_P n)。
    • 所以总时间复杂度是预处理加上所有查询的总和。

  • 空间复杂度: O(MAX_P)O(MAX\_P)

    • 我们需要一个大小为 MAX_P 的数组 partition_counts 来存储预计算的整数划分数，这是最主要的额外空间开销。

知识点总结 ​

这道题虽然伪装成了一道图论和组合问题，但它的核心却是一道数论题，喵~

  1. 排列的环结构: 任何一个排列都可以唯一地分解成若干个不相交的环。这和整数划分建立了联系。
  2. 整数划分 (Integer Partition): 将一个正整数 nn 分解成若干正整数之和的方案数。这是解决本题的关键概念之一。
  3. 欧拉五边形数定理: 提供了计算整数划分函数 p(k)p(k) 的一个高效递推式，是动态规划预处理的基础。
  4. 数论特殊定理: 解决本题的核心依赖于一个不那么广为人知的数论定理。这提醒我们，在算法竞赛中，有些问题可能需要特定的数学知识储备。遇到看似无法下手的计数题时，可以尝试搜索相关的数学定理。
  5. P进制分解: 最终的计算公式与数值的P进制表示紧密相关，这是一种在数论问题中常见的思想。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问我哦~ 喵~✨