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

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

首选程序为完整的单文件 std.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. 方案比较与验证¶

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

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

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

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

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

7.1 无序枚举后比较排序¶

排序版程序将剑分成两半。每加入一把剑，就遍历已有状态，将允许触发的状态乘上倍率和权重后追加到数组末尾。各层长度构成等比数列，因此枚举本身仍然只需 \(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 对每个左状态独立二分¶

二分版程序已经使用标程的有序归并建表，并预处理权重前缀和。回答询问时，对每个左状态 \((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})\) ，但多询问下的瓶颈不同。少询问、多次大规模建表限制比较排序；较小列表、大量询问限制逐项二分。两类数据分别检验了线性建表和线性查询这两个优化。