统计方案

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

折半搜索(Meet in the Middle)优化子集乘积枚举,费马小定理求逆元,特判处理元素为 0 和全空集情况。

OJ: roj

题目 ID: 5017

难度:提高+/省选-

标签:折半搜索乘法逆元快速幂

创建: 2026-10-08 20:07

更新: 2026-10-08 20:07

形式化题目

给定 nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n,从中至少选取一个数。问所有选取方案中,选出的数的乘积模质数 pp 的余数为 cc 的方案数有多少? 答案对 10000000071000000007 取模。

数据范围

  • n≤32n \le 32
  • p≤109p \le 10^9(pp 是质数)
  • c≤109c \le 10^9
  • ai<pa_i < p

正解

思路

这是一道利用折半搜索(Meet in the Middle)优化复杂度的题目。

朴素算法:枚举每个数选或不选,时间复杂度为 O(2n)O(2^n)。由于 n≤32n \le 32,232≈4.29×1092^{32} \approx 4.29 \times 10^9,直接搜索会超时。 因为 n/2≤16n/2 \le 16,216=655362^{16} = 65536,完全在可以承受的范围内。因此我们将数组分成两半,分别枚举子集的乘积,然后在中间合并配对。

  1. 分离出 0 的特判: 题面仅限制 ai<pa_i < p,并没有排除 ai=0a_i = 0。而 00 没有模逆元,不能直接参与同余方程的配对。 如果子集中包含了至少一个 00,那么整个子集的乘积一定是 00。 假设序列中有 zz 个 00,有 m=n−zm = n - z 个非零元素: 包含至少一个 00 的子集,只要我们从 00 中选出至少一个(方案数为 2z−12^z - 1),剩下的非零元素可以任意选配(方案数为 2m2^m),那么这样的集合一共有 (2z−1)⋅2m(2^z - 1) \cdot 2^m 个。

    • 当 c=0c = 0 时,所有这些集合都合法,计入 base 中。
    • 当 c≠0c \ne 0 时,所有这些集合都不合法,直接忽略。 剩下的事情,就是用不包含 00 的部分(共 mm 个数)走折半搜索。
  2. 折半搜索配对式推导: 将这 mm 个非零数平分成前后两半。 假设左半部分的组合乘积为 xx,右半部分乘积为 yy。我们需要满足 x⋅y≡c(modp)x \cdot y \equiv c \pmod p。 由于 pp 是质数,且 x≠0x \ne 0,xx 存在乘法逆元 x−1x^{-1}。 等式两边同乘 x−1x^{-1},可以得到 y≡c⋅x−1(modp)y \equiv c \cdot x^{-1} \pmod p。 其中 x−1x^{-1} 可以通过费马小定理结合快速幂求出:x−1≡xp−2(modp)x^{-1} \equiv x^{p-2} \pmod p。 因此,我们枚举左半部分所有子集的乘积 xx,计算出目标需求值 c⋅x−1(modp)c \cdot x^{-1} \pmod p 并存下;再枚举右半部分所有子集的乘积 yy,查表统计 yy 的出现次数。

  3. 空集扣减: 搜索时我们允许“一个都不选”(空集乘积视作 11)。如果左右两半都选了空集,此时乘积也是 11。 由于题目规定“至少取一个数”,当且仅当目标余数 c=1c = 1 时,这 11 种“全空集”的方案会被错误计入答案中,需要将其扣除:total -= 1。 需要注意的是,这一扣除只在 MITM 搜索逻辑中操作一次,前面特判 00 的 base 天然排除了“不选 00”的空集状态,不需要重复减。

代码

python
#!/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()
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-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;
}

复杂度

  • 时间复杂度: 前半部分枚举所有状态需要 O(2⌊m/2⌋)O(2^{\lfloor m/2 \rfloor})。 对每个状态求逆元使用快速幂的时间为 O(log⁡p)O(\log p)。 前半部分结果排序去重需要 O(m⋅2⌊m/2⌋)O(m \cdot 2^{\lfloor m/2 \rfloor})。 后半部分枚举所有状态并在二分查表的时间为 O(m⋅2⌈m/2⌉)O(m \cdot 2^{\lceil m/2 \rceil})。 总时间复杂度约为 O(2m/2log⁡p)O(2^{m/2} \log p),在 n=32n=32 时运算次数不会超过 2×1062 \times 10^6,完全可以通过。
  • 空间复杂度: 需要记录左半部分生成的状态并去重,需要约 O(2⌊m/2⌋)O(2^{\lfloor m/2 \rfloor}) 的空间,大小最大为 6553665536,因此空间复杂度极小。

总结

  • 题意与数据范围:n≤32n \le 32、pp 为质数、c≤109c \le 10^9、ai<pa_i < p。此外,题面写明了“至少取了一个数”,所以最终在空集的时候需要特判排空。
  • 为什么是 MITM:面对 n≤40n \le 40 且暴力穷举超时,状态可以通过某些结合律拆成两边配对的情况,首选折半搜索优化。
  • 配对式推导与逆元求法:通过左半积 xx、右半积 yy 的同余关系 xy≡c(modp)xy \equiv c \pmod p 可推导为 y≡c⋅x−1(modp)y \equiv c \cdot x^{-1} \pmod p(x≠0x \ne 0)。由于 pp 是质数,使用费马小定理即可知道 x−1≡xp−2(modp)x^{-1} \equiv x^{p-2} \pmod p。
  • ai=0a_i = 0 的处理(极易忽略的盲区):虽然测试数据没有 00,但题目条件仅说明 ai<pa_i < p 而未排除 00,00 无逆元,原版 MITM 会在此处错误判断。将 00 拿出来独立计数不仅弥补了逻辑缺陷,也能让剩余非零元素安心地进行逆元求解。这种特判项在应对 c=0c = 0 和 c≠0c \neq 0 时可以快速确定合法范围。
  • 空集扣减:MITM 中我们定义空集的积为 1,在当 c=1c=1 的时候,由于要求至少取一个数,左半边全空和右半边全空的配对不合法,必须减 1。
  • 两模数辨析:乘积/逆元操作都在  mod p\bmod p 域中进行;最终的方案数计算是累加,所有跟方案计数相关的 + 和 * 要用  mod (109+7)\bmod (10^9+7)。不要把求逆元的 pp 和方案数的模 109+710^9+7 混淆。
  • 反事实实验:如果你把对于 00 处理的 base 特判关掉(强行设 c=0 不触发),包含 00 的合法用例将会全部失效并输出错误结果,这再次佐证了特判项不仅是逻辑补全,也是承载正确答案的关键部位。