Grox的序列三题解¶

出题人解法：按阶乘下标分块，预处理带连续乘积的块内和。 Codex（GPT-6）整理 C++17 实现，补齐零下标、空和及末块边界。模数为合数，算法始终只使用加法和乘法，不需要阶乘逆元。

1. 同步移动两个下标¶

令 \(j=i+b-a\) .一次询问中，\(i\) 从 \(a\) 开始，\(j\) 从 \(b\) 开始，两者同步加一，直到某个下标超过 \(n\) .

维护已经经过的连续乘积 \(R\) ，初始为一。直接处理一项时：

\[ R\gets Ri,\qquad \mathrm{Ans}\gets\mathrm{Ans}+R\,j! \]

这样逐项计算显然正确，但每次需要 \(O(n+1)\) 时间。

取块宽 \(B=\lfloor\sqrt{n+1}\rfloor+1\) ，按阶乘下标 \(j\) 分块。块起点为 \(s\) .对于连续乘积的起点 \(x\) ，预处理

\[ H(s,x)=\sum_{k=0}^{B-1}(s+k)!\prod_{t=0}^{k}(x+t) \]

只保留 \(s+k\le n\) 且 \(x+k\le n\) 的项。另外保存完整长度块的乘积

\[ M(x)=\prod_{t=0}^{B-1}(x+t) \]

阶乘先用递推算出。枚举块起点与 \(x\) ，在块内依次乘入因子即可计算 \(H\) ，不进行模除法。

当 \(j\) 尚未对齐块起点，逐项处理。若当前 \(i,j\) 都还容得下一个完整块，则执行

\[ \mathrm{Ans}\gets\mathrm{Ans}+R\,H(j,i),\qquad R\gets R\,M(i) \]

然后把两个下标同时增加 \(B\) .末尾不足整块的部分逐项处理。所有运算都取模。

进入一个块之前的 \(R\) 是该块之前全部因子的乘积；\(H\) 的每一项只包含块内新增加的因子。因此 \(R H\) 恰好是这一块的原式贡献，\(R M\) 又是下一块所需的前缀乘积。由此归纳得到询问的正确答案。

若 \(a>n\) 或 \(b>n\) ，一开始就是空和。若 \(a=0\) ，包含零因子的乘积自然为零。\(n=0\) 时仍建立合法的一项阶乘数组。

记 \(N=n+1\) .预处理时间为 \(O(N^2)\) ；每次查询有至多两个不足整块的部分及 \(O(N/B)\) 个整块，时间为 \(O(B+N/B)\) .总时间为 \(O(N^2+q\sqrt N)\) ，空间为 \(O(N^2/B+N)=O(N\sqrt N)\) .

这个方案用比完整二维答案表更少的空间保留查询所需信息；没有修改出题人的分块策略。数组下标在访问前检查范围，乘法使用 64 位有符号整数：两个模数内余数之积小于 \(921260340^2\) ，在其范围内。

tests/generate.py 覆盖最大规模长区间、随机询问、零因子、末块与越界起点。小规模校验按题面计算精确整数阶乘及乘积，最后取模。编译标程后通过 --std 生成答案；参考时限见评测环境与性能。