Moe's CF Life

Appearance

C. Factorials and Powers of Two - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 774 (Div. 2) 标签: bitmasks, brute force, constructive algorithms, dp, math 难度: *1500

题目大意喵~ ​

喵~ 主人 sama，今天我们来解决一道有趣的题目哦！(ฅ'ω'ฅ)

题目定义了一种叫做 "powerful number"（强大数）的东西。一个数如果要么是 2的非负整数次幂（比如 1=2^0, 2=2^1, 4=2^2），要么是 非负整数的阶乘（比如 1=0! 或 1!, 2=2!, 6=3!），那它就是强大数啦。

我们的任务是，对于给定的一个正整数 n，找到一个最小的 k，使得 n 可以表示为 k 个 互不相同 的强大数的和。如果找不到这样的表示方法，就输出 -1。不过这道题保证总能找到解，所以我们不用担心 -1 的情况~

举个例子呐：n = 7，可以表示成 1 + 6。1 是 2^0，6 是 3!，它们都是强大数而且不相同，所以最少需要 2 个。

解题思路大揭秘！ ​

这道题看起来有点吓人，n 那么大 (可达 10^12)，直接去搜索所有组合肯定会超时的说 (´• ω •`)。但其实，这里面藏着一个非常重要的突破口哦！

突破口：飞速增长的阶乘！ ​

我们来观察一下阶乘的增长速度：

  • 3! = 6
  • 4! = 24
  • ...
  • 14! ≈ 8.7 * 10^10
  • 15! ≈ 1.3 * 10^{12}

看呐！15! 已经比题目给的 n 的最大值 10^12 还要大了。这意味着，在构造和为 n 的方案中，我们最多只会用到 14!。

再仔细看看，0! = 1, 1! = 1, 2! = 2。这些值本身就是2的幂 (1 = 2^0, 2 = 2^1)。为了避免重复和混淆（比如 1 到底是 1! 还是 2^0），我们可以把问题简化一下：

任何数 n 都可以看作是 “一些阶乘” 和 “一些2的幂” 的和。

由于 0!, 1!, 2! 已经是 2 的幂了，我们不如把它们就当作 2 的幂来处理。这样，我们需要考虑的阶乘就只有 3!, 4!, 5!, ..., 14! 这 12 个数了！

核心思路：暴力枚举 + 二进制拆分 ​

既然只有 12 个阶乘可供选择，这个数量非常小，小到我们可以暴力枚举所有选择它们的可能性！这正是 位掩码 (Bitmask) 大显身手的时候，喵~

我们可以用一个 12 位的二进制数（一个整数）来表示我们是否选择了这 12 个阶乘中的某一个。比如，二进制 ...00101 就表示我们选择了列表中的第 0 个和第 2 个阶乘。

我们的解题步骤就清晰啦：

  1. 预处理：先把 3! 到 14! 这 12 个阶乘算出来，存到一个列表里。
  2. 暴力枚举：用一个循环 for (int i = 0; i < (1 << 12); ++i) 来遍历所有 2^12 = 4096 种阶乘的组合（子集）。i 就是我们的位掩码。
  3. 计算与拆分：对于每一种组合 i：
    • 我们计算出这个组合中所有阶乘的总和 sum_fact，以及我们选了多少个阶乘 count_fact。
    • 如果 sum_fact > n，那这个组合肯定不行，直接跳过。
    • 否则，我们计算出剩下的部分 remainder = n - sum_fact。
    • 这个 remainder 必须用 2的幂 来凑成。任何一个正整数都可以唯一地表示成若干个不同的2的幂的和（这就是它的二进制表示！）。所以，凑成 remainder 需要的最少2的幂的数量，就是 remainder 在二进制表示下 1 的个数！
  4. 寻找最优解：
    • 对于当前的阶乘组合，总共需要的强大数个数就是 count_fact + (remainder 的二进制1的个数)。
    • 我们维护一个全局的最小值 min_k，每次计算出一个新的总个数，就和 min_k 比较并取较小值。
    • min_k 的初始值是什么呢？当然是完全不使用阶乘，只用2的幂来表示 n 的情况啦！也就是 n 的二进制中 1 的个数。

通过遍历所有 4096 种阶乘组合，我们一定能找到那个最优的 k 值！

代码实现喵~ ​

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

// 这个解决方案使用了 GNU G++ 的内置函数 __builtin_popcountll。
// 如果用 MSVC 等其他编译器，可能需要自己实现或者使用 <intrin.h> 里的函数。

// 喵~ 我们先把用得到的阶乘（3! 到 14!）算好放进一个列表里
// 为什么从3!开始呢？因为0!, 1!, 2! 都是2的幂，可以直接在二进制里处理，更方便喵~
// 14! 大约 8.7e10, 15! 大约 1.3e12，所以我们只需要到14!就够了
const std::vector<long long> non_power_of_two_factorials = {
    6LL,          // 3!
    24LL,         // 4!
    120LL,        // 5!
    720LL,        // 6!
    5040LL,       // 7!
    40320LL,      // 8!
    362880LL,     // 9!
    3628800LL,    // 10!
    39916800LL,   // 11!
    479001600LL,  // 12!
    6227020800LL, // 13!
    87178291200LL // 14!
};

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

    // min_k 的初始值，就是完全不用阶乘，只用2的幂来凑出 n 的情况。
    // 这等于 n 的二进制表示中 '1' 的数量。
    // __builtin_popcountll 是个超棒的函数，能直接数出一个 long long 里有多少个1！
    int min_k = __builtin_popcountll(n);

    int num_facts = non_power_of_two_factorials.size();
    
    // 用 bitmask 来遍历所有非空的阶乘组合，喵~ (1 << num_facts) 就是 2^12
    for (int i = 1; i < (1 << num_facts); ++i) {
        long long current_sum_fact = 0;
        int count_fact = 0;

        // 计算当前阶乘子集的和与大小
        for (int j = 0; j < num_facts; ++j) {
            // 检查第 j 位是不是 1，如果是就表示我们选中了第 j 个阶乘
            if ((i >> j) & 1) {
                current_sum_fact += non_power_of_two_factorials[j];
                count_fact++;
            }
        }

        // 如果当前阶乘子集的和已经小于等于 n，这才是一个有效的局部解
        if (current_sum_fact <= n) {
            long long remainder = n - current_sum_fact;
            
            // 剩下的部分 (remainder) 就全靠2的幂来凑齐！
            // 需要的2的幂的数量就是 remainder 二进制中 1 的个数
            int count_pow2 = __builtin_popcountll(remainder);
            
            // 总数量 = 用的阶乘数 + 用的2的幂的数量。更新我们找到的最小 k 值~
            min_k = std::min(min_k, count_fact + count_pow2);
        }
    }

    std::cout << min_k << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析的说~ ​

  • 时间复杂度: O(2^F * F) 的说。这里的 F 是我们考虑的阶乘数量，也就是 12。我们有一个主循环，遍历所有 2^F 个阶乘子集。在每个子集里，我们还要用一个 O(F) 的循环来计算和。因为 F 很小 (F=12)，所以 2^12 * 12 是一个非常小的计算量，这个速度非常快，完全没问题喵~
  • 空间复杂度: O(F) 的说。我们预计算并存储了 F 个阶乘，所以空间复杂度就是 O(F)。非常节省空间呢！

知识点与总结 ​

这道题真是个很好的例子，告诉我们如何处理看起来很复杂的问题！

  1. 数据范围是关键：看到 n 很大，但某个相关的集合很小（比如这里的阶乘数量），就要立刻想到可以暴力枚举这个小集合哦！这是一种常见的从约束中找突破口的方法。
  2. 位掩码 (Bitmask)：Bitmask 是枚举子集的超级好朋友！用一个整数就能优雅地代表一个集合的各种状态，是解决这类问题的经典工具。
  3. 二进制表示的妙用：任何正整数都可以唯一地表示为不同2的幂的和。这个性质在算法题中超级有用！计算需要多少个2的幂，就是数二进制里有多少个1，__builtin_popcount 系列函数是我们的好帮手！
  4. 组合与拆分思想：这道题的本质就是把 n 拆分成两部分：一部分由阶乘组成，另一部分由2的幂组成。我们暴力枚举第一部分的所有可能性，而第二部分的最优解是固定的（就是二进制拆分），这样就能找到全局最优解啦！

希望这篇题解能帮到主人 sama！继续加油，算法的世界还有很多好玩的等着我们去探索呢，喵~ (ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe