# Grox的序列二题解

**首选：按指数余数分类的前缀和，Codex（GPT-6）针对所需的三个总和给出线性算法。** 出题人的分治 NTT 解法可计算全部系数，下文保留完整思路及复杂度；本题只要求三个总和，因此 `std.cpp` 采用线性算法。

## 1. 只保留会影响输出的信息

令 $f_i=(i!)^{-1}\bmod P$ .一对非负整数 $(i,j)$ 在且仅在 $i+j\le n$ 时贡献一项，系数为 $f_if_j$ ，指数为 $i-j$ .

对固定 $i$ ，需要把 $0\le j\le n-i$ 的 $f_j$ 按 $j\bmod3$ 分成三组。定义

$$H_t(z)=\sum_{\substack{0\le j\le z\\j\equiv t\pmod3}}f_j$$

则

$$A_r=\sum_{i=0}^n f_iH_{(i-r)\bmod3}(n-i)\pmod P$$

余数统一正规化到 $0,1,2$ .

## 2. 一次扫描

先计算阶乘，再用一次快速幂得到 $f_n$ ，从大到小利用 $f_{i-1}=if_i$ 求出全部逆阶乘。

令 $i$ 从 $n$ 递减到零。每次加入新出现的 $j=n-i$ ，更新三个前缀和中的一项；随后按上述公式给三个答案分别增加贡献。因此不需要保存每个前缀，也不需要生成整个 Laurent 多项式。

循环处理 $i$ 时，三项前缀和恰好覆盖 $j=0,\ldots,n-i$ ，故每对合法 $(i,j)$ 在正确余数类别中被统计一次，非法数对没有进入前缀。由此证明输出正确。$n=0$ 自然得到 $1,0,0$ .

时间为 $O(n+\log P)$ ，空间为 $O(n)$ .若把固定模数的快速幂视为常数，则时间为 $O(n)$ .

## 3. 出题人解法：三角区域分治与 NTT

完整系数需要处理三角区域 $i+j\le n$ .令 $t=n-j$ ，于是 $0\le i\le t\le n$ ，对应项的指数为 $i+t-n$ ，系数为 $f_i f_{n-t}$ .

对区间 $[l,r]$ 的数对 $l\le i\le t\le r$ 做分治。设中点为 $h$ ：

1. 递归处理 $l\le i\le t\le h$ .
2. 递归处理 $h+1\le i\le t\le r$ .
3. 对跨区间矩形 $l\le i\le h<t\le r$ ，计算两个序列的卷积。

跨区间卷积取 $A_{i-l}=f_i$ 和 $B_{t-h-1}=f_{n-t}$ .下标和为 $k=(i-l)+(t-h-1)$ 的乘积应加入指数 $l+h+1+k-n$ .叶子 $i=t=l$ 则直接加入 $f_lf_{n-l}$ ，指数为 $2l-n$ .

每个合法数对在某个递归叶子或第一次分离的跨区间矩形中恰好出现一次，因此得到全部系数。用模 $P$ 、原根 $3$ 的 NTT 计算每个卷积，长度补到至少为两个序列长度之和减一的二次幂，避免循环卷积混叠。最后把指数 $e$ 的系数按 $e\bmod3$ 累加。

长度为 $s$ 的递归节点耗时 $O(s\log s)$ ，每层总长度为 $O(n)$ ，总时间 $O(n\log^2(n+2))$ .深度优先处理并复用工作数组，空间为 $O(n)$ ；逆阶乘可按第二节预处理。

分治 NTT 适合需要全部系数或更细系数询问的扩展规格。对于本题的三个总和，前缀和方法在渐进时间上更低，保留的信息也足够。这个比较不依赖未测量的程序运行速度。

## 数据与验证

样例包含 $n=0,1,3$ .正式数据覆盖二次幂附近与最大规模。小规模校验直接枚举全部合法 $(i,j)$ ，用独立求逆计算系数。数据生成入口为 `tests/generate.py` ；参考时限见[评测环境与性能](../../../docs/评测环境与性能.md)。