把每种金属在 k 个熔炉中的出现情况看成一个长度为 k 的 0/1 模式，合法模式有 2^k-1 种，总答案是 (2^k-1)^n。
OJ: luogu
题目 ID: P8557
难度:普及/提高-
标签:数学容斥快速幂思维
日期: 2026-06-20 06:57
题意
有 k 个熔炉，每个熔炉会炼出 n 种金属中的某个子集，也可能什么都没有。
如果把所有熔炉炼出的金属合并起来，包含了全部 n 种金属，就算成功炼出合金。
要求统计有多少种炼制情况，答案对 998244353 取模。
思路
先看一个可以直接验证的小数据暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int n, k;
int furnace_choose[20];
i64 ans = 0;
void dfs(int pos) {
if (pos == k + 1) {
int all_mask = 0;
for (int i = 1; i <= k; i++) {
all_mask |= furnace_choose[i];
}
if (all_mask == (1 << n) - 1) {
ans++;
}
return;
}
for (int mask = 0; mask < (1 << n); mask++) {
furnace_choose[pos] = mask;
dfs(pos + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
dfs(1);
cout << ans % 998244353 << '\n';
return 0;
}暴力版直接枚举每个熔炉炼出哪个子集，最后把它们按位或起来，看能不能覆盖全部金属。
不按熔炉想，按金属想
如果按熔炉来想，每个熔炉都有 2^n 种选择，整体看起来很乱。
但如果反过来按“某一种金属”来想，事情会非常简单。
固定某一种金属，它在 k 个熔炉里会出现成一个长度为 k 的 0/1 模式：
- 某个熔炉产出这种金属：记
1 - 没产出：记
0
这样的模式一共有：
2^k
种。
但如果全是 0，说明这种金属一个熔炉都没炼出来，那最终就不可能合成合金。
所以对每一种金属来说，合法模式数是：
2^k - 1
各种金属彼此独立
第 1 种金属在各熔炉里怎么出现，和第 2 种金属怎么出现，是互不影响的。
因此：
- 每种金属各有
2^k - 1种合法模式 - 一共
n种金属
直接用乘法原理得到答案：
(2^k - 1)^n
因为 n 和 k 都很大，所以需要两次快速幂。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 MOD = 998244353;
i64 quick_pow(i64 base, i64 exp) {
i64 ans = 1 % MOD;
base %= MOD;
while (exp > 0) {
if (exp & 1) {
ans = ans * base % MOD;
}
base = base * base % MOD;
exp >>= 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n, k;
cin >> n >> k;
i64 ways_for_one_metal = quick_pow(2, k) - 1;
if (ways_for_one_metal < 0) {
ways_for_one_metal += MOD;
}
cout << quick_pow(ways_for_one_metal, n) << '\n';
return 0;
}复杂度
两次快速幂：
- 时间复杂度
- 空间复杂度
总结
这题最关键的转换是：
- 不按熔炉枚举子集
- 改成按每种金属在
k个熔炉中的出现模式计数
一旦切换视角，答案就直接变成：
(2^k - 1)^n