# 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)$ 时间。

## 2. 整块预处理

取块宽 $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$ ，不进行模除法。

## 3. 询问处理

当 $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` 生成答案；参考时限见[评测环境与性能](../../../docs/评测环境与性能.md)。