Anya and Cubes

GitHub跳转原题关系图返回列表

折半枚举每个数的不选、原值、阶乘三种状态，按使用贴纸数统计目标和方案。

OJ: luogu

题目 ID: CF525E

难度:提高+/省选-

标签:Meet-in-the-Middle枚举计数python

日期: 2026-07-16 20:10

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

每个数可不选、按原值选、贴贴纸后按阶乘选，最多使用 k 张贴纸，统计和为 S 的方案数。

思路

直接三进制枚举是 3253^{25}。把数组分成两半，先枚举左半，把结果按贴纸数存为 sum -> 方案数；枚举右半叶子时，查询左半所有允许贴纸数中 S-right_sum 的出现次数。

a > 18 时 a! > 10^16，不可能进入合法总和，可省略阶乘分支。原值与阶乘即使相等也代表不同贴纸选择，两个递归分支都必须保留。

Python 知识

  • defaultdict(int) 自动累加重复元素产生的相同 (sum, stickers) 方案。
  • math.factorial 只预计算可用的小数值。
  • sum(mapping.get(key, 0) for ...) 汇总所有可接受贴纸数。

代码

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)

复杂度

时间约 O(3n/2k)O(3^{n/2}k)，空间 O(3n/2)O(3^{n/2})。

总结

折半搜索不仅拆“和”，还要保留贴纸数这一限制维度；按限制分桶能让合并保持直接。