折半搜索(Meet in the Middle)优化子集乘积枚举,费马小定理求逆元,特判处理元素为 0 和全空集情况。
OJ: roj
题目 ID: 5017
难度:提高+/省选-
标签:折半搜索乘法逆元快速幂
创建: 2026-10-08 20:07
更新: 2026-10-08 20:07
形式化题目
给定
数据范围
( 是质数)
正解
思路
这是一道利用折半搜索(Meet in the Middle)优化复杂度的题目。
朴素算法:枚举每个数选或不选,时间复杂度为
-
分离出 0 的特判: 题面仅限制
,并没有排除 。而 没有模逆元,不能直接参与同余方程的配对。 如果子集中包含了至少一个 ,那么整个子集的乘积一定是 。 假设序列中有 个 ,有 个非零元素: 包含至少一个 的子集,只要我们从 中选出至少一个(方案数为 ),剩下的非零元素可以任意选配(方案数为 ),那么这样的集合一共有 个。 - 当
时,所有这些集合都合法,计入 base中。 - 当
时,所有这些集合都不合法,直接忽略。 剩下的事情,就是用不包含 的部分(共 个数)走折半搜索。
- 当
-
折半搜索配对式推导: 将这
个非零数平分成前后两半。 假设左半部分的组合乘积为 ,右半部分乘积为 。我们需要满足 。 由于 是质数,且 , 存在乘法逆元 。 等式两边同乘 ,可以得到 。 其中 可以通过费马小定理结合快速幂求出: 。 因此,我们枚举左半部分所有子集的乘积 ,计算出目标需求值 并存下;再枚举右半部分所有子集的乘积 ,查表统计 的出现次数。 -
空集扣减: 搜索时我们允许“一个都不选”(空集乘积视作
)。如果左右两半都选了空集,此时乘积也是 。 由于题目规定“至少取一个数”,当且仅当目标余数 时,这 种“全空集”的方案会被错误计入答案中,需要将其扣除: total -= 1。 需要注意的是,这一扣除只在 MITM 搜索逻辑中操作一次,前面特判的 base天然排除了“不选”的空集状态,不需要重复减。
代码
#!/usr/bin/env python3
# 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-10-08 19:48
# update_at: 2026-10-08 19:57
import sys
from collections import Counter
MOD = 10**9 + 7 # 方案数的模,和题目给的质数 p 是两回事
def half_products(values: list[int], p: int) -> list[int]:
"""折半枚举:返回这一半所有子集(含空集)乘积 mod p 的列表。"""
prods = [1]
for v in values:
prods += [x * v % p for x in prods] # 每个已有子集再决定选不选 v
return prods
def count_schemes(a: list[int], p: int, c: int) -> int:
"""折半搜索:左半积 x 需要右半积 y 满足 x*y ≡ c (mod p),即 y ≡ c * x^{-1}。
0 没有模逆元,先把它们剔出来:设 z = 0 的个数、m = 剩余非零元素个数,
含至少一个 0 的非空子集共 (2^z - 1) * 2^m 个,它们的积恒为 0,故只在 c == 0 时全部合法。
"""
if c >= p: # 余数一定小于 p,不可能命中
return 0
zeros = a.count(0)
nz = [x for x in a if x != 0] # 非零元素才能进折半配对
half = len(nz) // 2
need = Counter(c * pow(x, p - 2, p) % p for x in half_products(nz[:half], p))
total = sum(need[y] for y in half_products(nz[half:], p)) # Counter 缺键默认 0
if c == 1:
total -= 1 # 减掉左右都取空集这一种(要求至少取一个数)
# c == 0 时含 0 的子集全部命中;c != 0 时它们全部落空,无需计入
zero_part = (pow(2, zeros, MOD) - 1) * pow(2, len(nz), MOD) % MOD if c == 0 else 0
return (total + zero_part) % MOD
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, p, c = next(data), next(data), next(data)
a = [next(data) for _ in range(n)]
print(count_schemes(a, p, c) % MOD)
if __name__ == "__main__":
solve()/**
* 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-10-08 19:48
* update_at: 2026-10-08 19:57
*/
// main.cpp:统计方案(一本通 1681,n<=32)。
// 折半搜索(meet in the middle)+ 费马小定理求逆元:
// 左半每个子集积 x 需要右半积 y 满足 x*y ≡ c (mod p),即 y ≡ c * x^{-1} (mod p)。
// 两半各有 2^(n/2) <= 2^16 个子集,右半每个积在左半“需求表”里二分查出现次数。
// 关于 0:题面只保证 a[i] < p,未排除 a[i] == 0,而 0 没有模逆元,不能进折半配对。
// 设 z 为 0 的个数,把 0 全部剔除后剩下 m = n - z 个非零元素:
// 含至少一个 0 的子集积恒为 0,共 (2^z - 1) * 2^m 个非空子集。
// 若 c == 0 它们全部合法,直接计入 base;若 c != 0 它们全部非法,忽略。
// 不含 0 的子集(必然可求逆)交给折半搜索处理。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL; // 方案数的模,和题目给的质数 p 是两回事
ll n, p, c;
ll zeroCount; // 原序列里 0 的个数
ll m; // 剔除 0 之后剩下的元素个数
ll b[40]; // b[1..m],原序列去掉所有 0 后的非零元素
vector<ll> needList; // 左半每个子集积 x 对应的“右半所需值” c * x^{-1} mod p
vector<pair<ll, ll> > needTab; // needList 排序去重后:(所需值, 出现次数),供右半二分
ll ans;
// 快速幂 x^e mod mod。p 为质数时,x^(p-2) 就是 x 在 mod p 下的逆元
ll qpow(ll x, ll e, ll mod) {
ll r = 1 % mod;
x %= mod;
while (e > 0) {
if (e & 1) r = r * x % mod; // p <= 1e9 < 2^30,r * x < 2^60,long long 不会溢出
x = x * x % mod;
e >>= 1;
}
return r;
}
// 枚举左半区间 [1, r] 的每个子集,把“右半所需值”记进 needList
void dfs_left(ll dep, ll r, ll prod) {
if (dep > r) {
// b[] 里没有 0,p 又是质数 ⇒ prod != 0,逆元必存在
needList.push_back(qpow(prod, p - 2, p) * c % p);
return;
}
dfs_left(dep + 1, r, prod); // 不选 b[dep]
dfs_left(dep + 1, r, prod * b[dep] % p); // 选 b[dep]
}
// 枚举右半区间 [half+1, m] 的每个子集,在 needTab 里查这个积出现了几次
void dfs_right(ll dep, ll r, ll prod) {
if (dep > r) {
auto it = lower_bound(needTab.begin(), needTab.end(), make_pair(prod, 0LL));
if (it != needTab.end() && it->first == prod) ans = (ans + it->second) % MOD;
return;
}
dfs_right(dep + 1, r, prod);
dfs_right(dep + 1, r, prod * b[dep] % p);
}
void solve() {
if (scanf("%lld %lld %lld", &n, &p, &c) != 3) return;
zeroCount = 0;
m = 0;
for (ll i = 1; i <= n; i++) {
ll x;
scanf("%lld", &x);
x %= p;
if (x == 0) zeroCount++;
else b[++m] = x; // 0 单独计数,不放进折半数组
}
if (c >= p) { // 余数一定小于 p,c >= p 时一组都凑不出来
printf("0\n");
return;
}
// 含至少一个 0 的非空子集个数:(2^zeroCount - 1) * 2^m
ll base = 0;
if (c == 0) {
base = (qpow(2, zeroCount, MOD) - 1 + MOD) % MOD;
base = base * qpow(2, m, MOD) % MOD;
}
ll half = m / 2;
dfs_left(1, half, 1); // 空集也参与:左半空集的积是 1
sort(needList.begin(), needList.end());
ll total = needList.size();
for (ll i = 0; i < total; ) {
ll j = i;
while (j < total && needList[j] == needList[i]) j++;
needTab.push_back(make_pair(needList[i], j - i));
i = j;
}
dfs_right(half + 1, m, 1); // 空集也参与
// 题面要求“至少取一个数”:c == 1 时左右都取空集也被计入了,扣掉这一种
if (c == 1) ans = (ans - 1 + MOD) % MOD;
ans = (ans + base) % MOD;
printf("%lld\n", ans);
}
int main() {
solve();
return 0;
}复杂度
- 时间复杂度:
前半部分枚举所有状态需要
。 对每个状态求逆元使用快速幂的时间为 。 前半部分结果排序去重需要 。 后半部分枚举所有状态并在二分查表的时间为 。 总时间复杂度约为 ,在 时运算次数不会超过 ,完全可以通过。 - 空间复杂度:
需要记录左半部分生成的状态并去重,需要约
的空间,大小最大为 ,因此空间复杂度极小。
总结
- 题意与数据范围:
、 为质数、 、 。此外,题面写明了“至少取了一个数”,所以最终在空集的时候需要特判排空。 - 为什么是 MITM:面对
且暴力穷举超时,状态可以通过某些结合律拆成两边配对的情况,首选折半搜索优化。 - 配对式推导与逆元求法:通过左半积
、右半积 的同余关系 可推导为 ( )。由于 是质数,使用费马小定理即可知道 。 的处理(极易忽略的盲区):虽然测试数据没有 ,但题目条件仅说明 而未排除 , 无逆元,原版 MITM 会在此处错误判断。将 拿出来独立计数不仅弥补了逻辑缺陷,也能让剩余非零元素安心地进行逆元求解。这种特判项在应对 和 时可以快速确定合法范围。 - 空集扣减:MITM 中我们定义空集的积为 1,在当
的时候,由于要求至少取一个数,左半边全空和右半边全空的配对不合法,必须减 1。 - 两模数辨析:乘积/逆元操作都在
域中进行;最终的方案数计算是累加,所有跟方案计数相关的 +和*要用。不要把求逆元的 和方案数的模 混淆。 - 反事实实验:如果你把对于
处理的 base特判关掉(强行设c=0不触发),包含的合法用例将会全部失效并输出错误结果,这再次佐证了特判项不仅是逻辑补全,也是承载正确答案的关键部位。