(t, n) 门限的组合构造

· · 算法·理论

(t, n) 门限的组合构造

写在比较前面：年初搞出这个构造以为是 adhoc 的东西就丢到草稿箱里面了，然后就是这个结构越想越巧妙，在今年 CSP-S 初赛惊出现在到谋道程序填空题中,所以记录一下这个碎片模型的感觉。

对于 CSP-S 的程序填空题，好像很多人用更厉害的分析技巧做出来了，具体见 __Cby___ 写的文章 谁说完善程序一定要看题目描述的

标签：(t, n) 门限，组合，构造，CSP-S 2025 程序填空题

阅读顺序：从上到下

Part 1：怎么想到的？Threshold Scheme 和碎片模型

(t, n) 门限问题 是说我们怎么样可以将一个 秘密 拆解或分配给 n 个人，使得：

很难不发现能否还原秘密在人数上有单调性，如果任意 t 个人都可以恢复信息，显然任意 t+1 个人都可以恢复信息。所以我们需要一种方案，使得任意 t 个人都可以恢复信息，且任意 t-1 都不能恢复信息。

我们考虑随便试试简单的情况，比如对于 3 个人，任意 2 个人都可恢复信息：

分析一下碎片的本质，对于一个碎片 a，用集合 A\subseteq\{1,\cdots,n\} 表示拥有碎片 a 的人，\overline{A}=\{1,\cdots,n\}-S 表示没有碎片 a 的人，那么碎片 a 的作用是说至少需要 A 中的一个人才可以还原秘密，它的逆否命题是：

所以设置碎片 a 的意义是 禁用 \overline{A} 的所有子集！

于是我们可以设置碎片禁用掉所有大小为 t-1 的子集，就可以得到满足要求的构造：

正确性证明：

这个 碎片模型 喵述了碎片禁用人的子集的限制关系，但是我们可以举一反三，对于 (t, n) 门限问题是固定了人数和门限数 t，但是其实我们只要 人数，门限数，碎片数 任意确定两个就可以构造出剩下的一个。对于构造的关键感觉有三个：

下面两个问题分别介绍 “限制人和碎片” 和 “限制碎片和门限” 构造剩下一种的思路。

Part 2：CF1365G Secure Password

题目链接：https://codeforces.com/problemset/problem/1365/G

题意：这是一道交互题，有一个隐藏的数组 A_{[1,n]}\in[0,2^{63}-1]，你可以问 jury 最多 13 个问题，每次提问你给 jury 若干位置，jury 会告诉你 A 数组这些位置元素的位或和，你需要求出数组 P_i 表示 A 数组除了第 i 个位置的元素的位或。2\le n\le 1000。

以下是解题思路：

我们希望询问能恰好拼出缺少一个位置，所以将每个位置看作碎片，每次询问表示一个人有哪些碎片，这里确定了人的数量，为了让碎片数量（支持的原题的位置数）更多，门限数量应该选择靠近一半的位置（这里用到的只有人可以唯一定位一个碎片的性质，所以门限不重要）。

有 13 个人，所以我们把门限定为 t=7，则我们可以有 \binom{13}{7-1}=1716 个碎片，因为我们只利用人可以唯一定位一个碎片的性质，所以只保留前面 n 个碎片就好，分配方式是，对于所有 \{1,\cdots,n\} 的大小为 6 的子集 S，将碎片 a_S（对应到数组的一个下标）给到所有 \overline{S} 中的人。

然后每个人问它有的碎片的所有位置。

对于下标 a_S，除了它的其他位置的位或就是 \overline{S} 中的人的答案的位或，因为这些人拥有除了 a_S 的所有其它碎片（也就是所有其它位置）。

Part 3：2025 CSP-S 初赛 程序填空 第二题

题意：有 n 个物品（编号 0\sim n-1），已知其中 一个 物品有缺陷。你可以做很多轮测试，每一轮测试为选择一个物品集合 S 发给客户，若 S 包含有缺陷的物品则客户返回 1（表示退货），否则客户返回 0（表示收货）。要求所有轮测试 最多 只能有 k 次退货。设计最少的测试轮数 w，可以唯一确定有缺陷的物品。

以下是解题思路：我们从做题（不是破解填空题）的角度审视这个情况。

从需要唯一定位缺陷的物品可以想到利用碎片模型的唯一定位的性质，这里将物品看作碎片，一次测试（也就是客户）对应一个人，我们要确定最小的测试轮数 w（也就是碎片模型的人数 n），使得最多 k 次退货。

每个碎片都有可能是缺陷的，所以题目要求是每个碎片拥有它的人数不能超过 k，而我们知道门限 t 是恰好有 n-(t-1) 人拥有某个碎片，所以 t\ge w-k+1。

因为门限 t 可以让每个人的组合唯一定位到任意一个 \binom{n}{t-1} 个碎片，想要轮数 w 尽量少，我们就需要为 w 个人设置尽量多的碎片，所以可以 同时 使用所有门限的所有碎片。

程序中的，count_patterns(w, k) 是计算确定有 w 个人，每个碎片最多被 k 人拥有的最多碎片数量。main 函数中第一步用这个函数枚举出最小的人数 w 使得支持定位足够多的碎片数量。

18 // 计算长度为 w、1 的个数 ≤ k 的码字总数
19 long long count_patterns(int w, int k) {
20     long long total = 0;
21     for (int t = 0; t <= min(w, k); ++t) {
22         total += comb(w, t);
23     }
24     return total;
25 }
...
31     // === 第 1 步：求最小 w ===
32     int w = 1;
33     while (___①___) {
34         ++w;
35     }
36     cout << w << endl;

程序中的第二部就是用排列二进制来枚举所有碎片应该分给那些人。

38     // === 第 2 步：生成测试方案 ===
39     vector<vector<int>> code(n, vector<int>(w, 0));
40     int idx = 0;
41     for (int ones = 0; ones <= k && idx < n; ++ones) {
42         vector<int> bits(w, 0);
43         fill(bits.begin(), bits.begin() + ones, 1);
44         do {
45             for (int b = 0; b < w; ++b) {
46                 code[idx][b] = bits[b];
47             }
48             ++idx;
49             if (idx >= n) {
50                 break;
51             }
52         } while (std::___②___);
53     }

然后在第三步拿到每个人的结果，第四步根据任何人的集合可以唯一定位对应门限的一个碎片的性质，定位有问题的，这一步和 Part 2 Secure Password 中的定位是一样的。

64     // === 第 3 步：调用测试接口 ===
65     int signature = test_subset(plan);
66
67     // === 第 4 步：结果解码 ===
68     vector<int> sig_bits(w, 0);
69     for (int i = 0; i < w; ++i) {
70         if (___④___) {
71             sig_bits[i] = 1;
72         }
73     }
74
75     for (int j = 0; j < n; ++j) {
76         if (___⑤___) return j;
77     }

于是我们就从头解决了这个问题

。_。