折半枚举每个数的不选、原值、阶乘三种状态，按使用贴纸数统计目标和方案。
OJ: codeforces
题目 ID: 525E
难度:提高+/省选-
标签:Meet-in-the-Middle枚举计数python
创建: 2026-07-16 20:10
更新: 2026-10-28 17:33
题意
每个数可不选、按原值选、贴贴纸后按阶乘选，最多使用 k 张贴纸，统计和为 S 的方案数。
思路
直接三进制枚举是 sum -> 方案数；枚举右半叶子时，查询左半所有允许贴纸数中 S-right_sum 的出现次数。
a > 18 时 a! > 10^16，不可能进入合法总和，可省略阶乘分支。原值与阶乘即使相等也代表不同贴纸选择，两个递归分支都必须保留。
Python 知识
defaultdict(int)自动累加重复元素产生的相同(sum, stickers)方案。math.factorial只预计算可用的小数值。sum(mapping.get(key, 0) for ...)汇总所有可接受贴纸数。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-02
* update_at: 2026-08-02
*/
/* CF525E Anya and Cubes */
/* 三进制枚举是 3^25；折半搜索：左半枚举后按贴纸数分桶存 sum->方案数，
* 右半枚举叶子时查左半所有允许贴纸数的桶，累加 S-right_sum 的出现次数。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25 + 5;
int n, k; // n 个数，最多 k 张贴纸
long long S; // 目标和
long long a[MAXN]; // 每个数
long long fact[19] = {1}; // fact[i] = i!，只到 18（19! > 1e16 > S 上限）
// left[st]：左半枚举结果中，用了 st 张贴纸时的 sum -> 方案数
vector<unordered_map<long long, long long>> left_map;
// 枚举左半 [idx, end)，当前和 sum、已用贴纸 st
void dfs_left(int idx, int end, long long sum, int st) {
if (idx == end) {
left_map[st][sum]++;
return;
}
dfs_left(idx + 1, end, sum, st); // 不选
dfs_left(idx + 1, end, sum + a[idx], st); // 选原值
if (a[idx] <= 18 && st < k) // 选阶乘（贴一张贴纸）
dfs_left(idx + 1, end, sum + fact[a[idx]], st + 1);
}
long long ans = 0;
// 枚举右半 [idx, end)
void dfs_right(int idx, int end, long long sum, int st) {
if (idx == end) {
// 左半还能用 st2 张：st + st2 <= k
for (int st2 = 0; st2 + st <= k; st2++) {
auto it = left_map[st2].find(S - sum);
if (it != left_map[st2].end())
ans += it->second;
}
return;
}
dfs_right(idx + 1, end, sum, st);
dfs_right(idx + 1, end, sum + a[idx], st);
if (a[idx] <= 18 && st < k)
dfs_right(idx + 1, end, sum + fact[a[idx]], st + 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 1; i <= 18; i++)
fact[i] = fact[i - 1] * i;
cin >> n >> k >> S;
for (int i = 0; i < n; i++)
cin >> a[i];
left_map.resize(k + 1);
int mid = n / 2;
dfs_left(0, mid, 0, 0);
dfs_right(mid, n, 0, 0);
cout << ans << '\n';
return 0;
}python
import math
import sys
from collections import defaultdict
n, sticker_limit, target = map(int, sys.stdin.buffer.readline().split())
values = list(map(int, sys.stdin.buffer.readline().split()))
middle = n // 2
factorials = [math.factorial(value) if value <= 18 else None for value in values]
left_count = [defaultdict(int) for _ in range(sticker_limit + 1)]
def enumerate_left(index, end, total, stickers):
if total > target or stickers > sticker_limit:
return
if index == end:
left_count[stickers][total] += 1
return
enumerate_left(index + 1, end, total, stickers)
enumerate_left(index + 1, end, total + values[index], stickers)
factorial = factorials[index]
if factorial is not None:
enumerate_left(index + 1, end, total + factorial, stickers + 1)
enumerate_left(0, middle, 0, 0)
answer = 0
def enumerate_right(index, total, stickers):
global answer
if total > target or stickers > sticker_limit:
return
if index == n:
needed = target - total
answer += sum(left_count[used].get(needed, 0)
for used in range(sticker_limit - stickers + 1))
return
enumerate_right(index + 1, total, stickers)
enumerate_right(index + 1, total + values[index], stickers)
factorial = factorials[index]
if factorial is not None:
enumerate_right(index + 1, total + factorial, stickers + 1)
enumerate_right(middle, 0, 0)
print(answer)复杂度
时间约
总结
折半搜索不仅拆"和"，还要保留贴纸数这一限制维度；按限制分桶能让合并保持直接。