前情提要：社论「不 CDQ 的分治 NTT」(详细揭秘)
问题.
给定 q 组询问，每组询问给定 n, m，求
\sum_{i=1}^m \binom ni
其中各参数同阶（实际上只需要 m, q 同阶）。
我们直接泛化为 \mathbf V_{n, m} = \mathbf V_{n, m-1} \mathbf M_m(n)，其中 \mathbf V, \mathbf M 是多项式矩阵（或向量），要对这个递推式多点求值。
这里我们只需令 \mathbf V_{n, m} = \begin{bmatrix}\binom nm & \sum_{i=1}^m \binom ni\end{bmatrix}，\mathbf M_m(n) = \begin{bmatrix}\frac{n-m+1}m & \frac{n-m+1}m \\ 0 & 1 \end{bmatrix}。
那么问题变为多次查询多项式矩阵列 \mathbf M_k(x) 的某个前缀积的一处点值。熟悉传统的取模多点求值算法的读者，在将问题转化到这一步时就应当容易得到做法：分治取模即可。时间复杂度 O(n\log^2 n)。
事实上我们还有规避取模的做法，可以用来减小一点常数。
不妨假设每个前缀恰好需要一处点值，则问题可以描述为
a_m = \prod_{i=1}^m \mathbf M_i(x_m)
令 M = \max m，考虑一个 1 \times M 的矩阵 \mathbf A_{1m} = \prod_{i=1}^m \mathbf M_i(x_m)，从而该问题的转置为：给定序列 a'_m，求
\sum_{m=1}^M a'_m \prod_{i=1}^m \mathbf M_i(x_m)
考虑 F(x_0) = [t^0] \frac{F(1/t)}{1 - x_0 t}。不妨设 \deg \mathbf M_i(t) = 1，那么我们可以考虑计算
[t^M] \sum_{m=1}^M a'_m \frac{t^M \prod_{i=1}^m\mathbf M_i(1/t)}{1-x_m t} = [t^M] \sum_{m=1}^M a'_m \frac{t^{M-m} \prod_{i=1}^m\mathbf M_i^R(t)}{1-x_m t}
其中 F^R(t) 表示将 F(t) 的系数反转。
这样就规避了取模。同时转置后的问题也在一些地方已经出现，例如 CCPC Final 2022 M。