# 整除阈值 DP 与有序折半枚举

出题人解法：按参数规模结合整除阈值 DP 与有序折半枚举。Codex（GPT-6）：两种算法的应用与推导，设计多询问规格、模概率实现、整数溢出处理及验证数据。整除分块和折半枚举均为已有算法技巧，不作为原创技巧署名。

首选程序为完整的单文件 [std.cpp](std.cpp)。另有以时间换空间的[四分流式解法](solution-alternative-streaming.zh.md)与[计算程序](alternative-streaming.cpp)。

## 1. 概率与预处理

记 $D=10^6$ 、$P=998244353$ 、$a_i=p_iD^{-1}\bmod P$ .对概率使用模运算，对倍率使用精确整数运算，两者不能混用。

- $p_i=0$ 或 $m_i=1$ 的剑可以删除。
- $p_i=D$ 的剑必定贡献 $m_i$ 倍。删除它，并把每个询问的阈值改为 $\lceil K_j/m_i\rceil$ .
- 阈值为 $1$ 的答案恒为 $1$ .

确定倍率的除法必须向上取整。例如必定提供 $3$ 倍时，原阈值 $5$ 要求其余剑至少达到 $2$ 倍。

以下推导中的 $n$ 指剩余剑数。所有剩余剑都满足 $0<p_i<D$ ，故失败概率及其模逆均有定义。预处理不会增加阈值或剑数；空集合的倍率仍为 $1$ .若没有剩余剑，直接根据调整后的阈值是否为 $1$ 输出答案，不再建立 DP 或枚举列表。

## 2. 小阈值：累计概率 DP

先处理一个阈值 $K>1$ ，令 $T=K-1$ .设 $F_i(t)$ 为前 $i$ 把剑的倍率不超过整数 $t$ 的概率。按第 $i$ 把剑是否触发分类：

$$
F_i(t)=(1-a_i)F_{i-1}(t)+a_iF_{i-1}(\lfloor t/m_i\rfloor)
$$

初始值为 $F_0(0)=0$ ，对 $t\ge1$ 有 $F_0(t)=1$ .答案为 $1-F_n(T)$ ，减法也在模 $P$ 意义下进行。

直接枚举所有阈值需要 $O(nK)$ 时间。但从 $T$ 出发，只有下面的阈值可能被访问：

$$
\mathcal Q_T=\{0\}\cup\{\lfloor T/d\rfloor:1\le d\le T\}
$$

这是因为整数乘法满足：

$$
\left\lfloor\frac{\lfloor T/d\rfloor}{m_i}\right\rfloor=\left\lfloor\frac{T}{dm_i}\right\rfloor
$$

当 $d\le\sqrt T$ 时，分母只有 $O(\sqrt T)$ 个；当 $d>\sqrt T$ 时，商小于 $\sqrt T$ .所以状态数只有 $O(\sqrt K)$ ，且对转移封闭。

### 数组下标，不用哈希或二分

令 $s=\lfloor\sqrt T\rfloor$ 、$r=\lfloor T/(s+1)\rfloor$ .按升序存储 $0,1,\ldots,s$ ，再存储分母从 $r$ 递减至 $1$ 时的商。任一非零状态 $t$ 的下标为：

$$
\operatorname{index}(t)=
\begin{cases}
t,&t\le s,\\
s+r-\lfloor T/t\rfloor+1,&t>s
\end{cases}
$$

每次转移在常数时间内定位目标。处理一把剑时按阈值从大到小更新，使较小阈值仍保留上一层的值，因此只需一个概率数组。

归纳证明：初始数组表示空集合；每次转移将不触发和触发两类互斥事件的概率相加，状态集合又没有遗漏依赖，因此最终数组就是所定义的累计概率。

对全部询问分别计算，时间为 $O(n\sum_j\sqrt{K_j})$ ，额外状态空间为 $O(\sqrt{K_{\max}})$ ，其中 $K_{\max}=\max_jK_j$ .

## 3. 小剑数：有序折半枚举

令 $M=\max_j K_j$ .仍先计算不达标的概率，再用 $1$ 减去它。将剑分成尽量等大的两组，每组枚举触发集合及其倍率、概率权重。

### 共同概率因子

先提出所有剑都不触发的共同因子：

$$
C=\prod_i(1-a_i),\qquad w_i=\frac{a_i}{1-a_i}=\frac{p_i}{D-p_i}\pmod P
$$

触发集合 $S$ 的概率为 $C\prod_{i\in S}w_i$ .因此，建表时不触发的权重保持不变，触发的权重乘 $w_i$ ，两半合并后再乘 $C$ .预处理已删除必定触发的剑，分母均可逆。

### 在线性总时间内建表

维护按倍率升序排列的列表。加入一把剑时，原列表和把原列表各倍率乘 $m_i$ 后的列表分别有序，用线性归并得到下一层。

只保留倍率小于 $M$ 的状态。因为所有倍率至少为 $1$ ，一旦某个部分乘积达到 $M$ ，继续乘其他倍率也不可能属于任何询问的不达标事件。每次归并前，只允许原倍率不超过 $\lfloor(M-1)/m_i\rfloor$ 的状态触发。这既安全剪枝，也保证实际执行的乘法结果小于 $M$ .

一组有 $h$ 把剑时，各层长度最多为 $1,2,4,\ldots,2^h$ ，所以归并总时间为 $O(2^h)$ .实现中每层仅二分一次以找到可触发的前缀，其总成本 $O(h^2)$ 也被 $O(2^h)$ 包含。不能对每个状态都二分，也不需要在枚举完以后进行比较排序。

归纳可知，每个保留的状态对应一个触发集合，且全部倍率小于 $M$ 的集合都被保留。相同倍率的不同集合可以分别保留，其权重都必须计入。

### 前缀权重与双指针

记左右列表为 $(x_i,u_i)$ 和 $(y_j,v_j)$ .询问 $K$ 的不达标概率为：

$$
C\sum_i u_i\sum_{j:x_iy_j<K}v_j\pmod P
$$

对正整数有：

$$
x_iy_j<K\iff y_j\le\left\lfloor\frac{K-1}{x_i}\right\rfloor
$$

预先计算左右列表的权重前缀和，供全部询问共用。按升序枚举 $x_i<K$ ；从右列表末尾向前移动指针，直到保留的前缀恰好满足上式。随着 $x_i$ 增加，允许的右侧上界只会减小，每个右状态最多经过一次。直接读取右侧前缀权重即可计算当前贡献，最后取补事件得到答案。

标程把连续使用相同右前缀权重的左状态合并结算。若左前缀权重为 $U_i$ ，区间 $[l,r]$ 的权重就是 $U_r-U_{l-1}$ .这只利用模加法的线性性质，不改变整数倍率的判断规则。概率乘积每累计八项取一次模，以减少常数；逐项取模也具有相同复杂度。

所有左右触发集合互相独立，每个不达标配对都恰好被计入一次，因此该算法正确。令 $N=2^{\lceil n/2\rceil}$ ，建表和前缀和共需 $O(N)$ 时间，一次查询需 $O(N)$ 时间，全部查询为 $O(qN)$ .概率求逆另需 $O(n\log P)$ 时间，枚举空间为 $O(N)$ .

## 4. 全部运算只用有符号 64 位整数

输入满足 $K_j\le10^{18}<2^{63}-1$ .算法不计算完整的全部剑倍率，也不直接计算两个半边倍率的乘积。

- 生成状态时，先判断 $x\le\lfloor(M-1)/m\rfloor$ ，满足条件才计算 $xm$ ，结果严格小于 $M$ .
- 查询时，用 $y\le\lfloor(K-1)/x\rfloor$ 代替 $xy<K$ ，不做可能溢出的乘法。
- 确定触发剑的向上整除写为 $(K-1)/m+1$ ，避免先计算 $K+m-1$ .
- 平方根用逐位试探和除法比较计算，不使用浮点数。
- 单次概率模乘小于 $(P-1)^2<10^{18}$ ；DP 中两项之和小于 $2\cdot10^{18}$ ，均在 `int64_t` 内。

批量累加概率乘积时，已有的模余数加八项的最大值满足：

$$
(P-1)+8(P-1)^2<2^{63}-1
$$

所以每八项归约一次也不会溢出。中间过程不用扩展整数类型，不实现大整数，也不需要对数或误差容忍。

## 5. 算法选择与完整复杂度

比较整除 DP 和枚举、查询的估算工作量，选择较小者。剑数超过 $44$ 时，题目保证阈值较小，直接使用 DP。

计入概率求逆，一个测试组的时间复杂度为：

$$
O\left(n\log P+\min\left\{n\sum_j\sqrt{K_j},\ (q+1)2^{\lceil n/2\rceil}\right\}\right)
$$

这里的 $n,K_j$ 为预处理后的参数；另计读取原输入和确定触发剑的 $O(n_{\mathrm{原}}q)$ 阈值调整。DP 空间为 $O(n+q+\sqrt{K_{\max}})$ ，折半枚举空间为 $O(n+q+2^{\lceil n/2\rceil})$ .整数宽度有固定上界，以上按固定宽度整数运算计数。

只有折半枚举无法处理大剑数组，只有整除 DP 无法处理大阈值组。比较排序版的时间为 $O((n+q)N)$ ；逐状态二分版为 $O(qnN)$ .少询问、多次大规模建表的数据限制前者，较小枚举规模配合大量询问的数据限制后者。

## 6. 方案比较与验证

[四分流式方案](solution-alternative-streaming.zh.md)把枚举空间降至 $O(2^{\lceil n/4\rceil})$ ，但需要堆维护，无法通过完整时限。它适合内存更紧、允许更多时间的环境；双语说明和源码一并提供。

[std.cpp](std.cpp) 是完整、可单文件编译和提交的 C++17 程序，只包含标准库头文件。辅助验证程序通过定义 `SWORDS_LIBRARY_ONLY` 来复用其中的函数；正常编译标程不需要定义这个宏。

验证包含独立小规模枚举、强制交叉执行两种算法、整数边界、概率边界、样例和输入校验。性能比较使用共享剪枝、前缀和、区间权重结算及批量模乘的排序版和二分版。五次计时与源码、输入哈希见[测试说明](tests/README.md)和[测量记录](../../../docs/benchmark-swords-and-crits.json)。有限测试描述具体实现的表现，不构成对所有同阶程序的下界证明；目标评测机需要重新校准。

## 7. 两种正确但会超时的实现

下面两份程序都保留小阈值的整除 DP，只改变折半枚举分支。它们得到的答案正确，但提供的实现不能通过完整时限。仍令 $N=2^{\lceil n/2\rceil}$ ，以下复杂度省略共同的输入预处理和 $O(n\log P)$ 概率求逆开销；空间均为 $O(n+q+N)$ .

### 7.1 无序枚举后比较排序

[排序版程序](tests/slow-sort.cpp)将剑分成两半。每加入一把剑，就遍历已有状态，将允许触发的状态乘上倍率和权重后追加到数组末尾。各层长度构成等比数列，因此枚举本身仍然只需 $O(N)$ 时间；但数组没有保持有序，必须对左右两份数组分别调用 `std::sort` ，才能计算前缀权重并使用双指针回答询问。

它与标程枚举了相同的触发集合，使用相同的乘前剪枝，排序只改变状态顺序，因此后续概率计算仍然正确。额外开销来自比较排序：每半最多有 $N$ 个状态，排序需要 $O(N\log N)=O(nN)$ 时间。建表后的每次查询仍为 $O(N)$ ，总时间为：

$$
O(N\log N+qN)=O((n+q)N)
$$

这项排序开销只在每套剑建表时发生一次，可以被同一套剑的大量询问摊薄。因此，第 08 个正式测试点包含五套独立的 $n=44,q=1$ 数据：每套都要重新建立大列表，又只有一次询问。倍率取互不相同的整数，不能直接按相同剑倍率合并。参考环境下，该程序在此测试点的五次运行中位数约为 **2.932 秒**，超过 **2 秒**时限。

标程的改进在于每加入一把剑时就归并两个已经有序的列表，累计只做 $O(N)$ 次状态处理，从而消去建表阶段的 $\log N$ 因子。

### 7.2 对每个左状态独立二分

[二分版程序](tests/slow-binary.cpp)已经使用标程的有序归并建表，并预处理权重前缀和。回答询问时，对每个左状态 $(x,u)$ 单独计算：

$$
L=\left\lfloor\frac{K-1}{x}\right\rfloor
$$

随后在整个右列表中调用 `std::upper_bound` ，找到第一个倍率大于 $L$ 的位置。它之前的前缀恰好包含全部满足 $xy<K$ 的右状态，取出前缀权重乘以 $u$ 即为当前贡献；累加后取补事件，仍能得到正确答案。

问题在于，每个左状态都重新进行一次 $O(\log N)$ 的搜索。一次询问需要 $O(N\log N)=O(nN)$ 时间，全部询问连同建表需要：

$$
O(N+qN\log N)=O(qnN)
$$

这里额外的因子出现在每次查询中。因此，第 09 个正式测试点使用 $n=28,q=5600$ ：枚举列表较小，但同一套列表要反复回答大量询问。所有倍率均为互不相同的质数，不同子集的乘积也互不相同，不能通过合并重复乘积大幅缩小列表。参考环境下，该程序在此测试点的五次运行中位数约为 **2.627 秒**，超过 **2 秒**时限。

标程利用左倍率递增时 $L$ 单调不增的性质，让右指针只向前缀的左端移动。一次询问中，所有状态合计只被扫描 $O(N)$ 次；逐项二分没有复用这一单调性。

### 7.3 复杂度对照

| 折半枚举的实现 | 建表 | 单次查询 | 全部查询连同建表 |
| --- | --- | --- | --- |
| 有序归并与双指针（标程） | $O(N)$ | $O(N)$ | $O((q+1)N)$ |
| 无序枚举、比较排序与双指针 | $O(nN)$ | $O(N)$ | $O((n+q)N)$ |
| 有序归并与逐项二分 | $O(N)$ | $O(nN)$ | $O(qnN)$ |

当 $q=1$ 时，两种慢实现的复杂度都是 $O(n2^{\lceil n/2\rceil})$ ，但多询问下的瓶颈不同。少询问、多次大规模建表限制比较排序；较小列表、大量询问限制逐项二分。两类数据分别检验了线性建表和线性查询这两个优化。