ARC120F2

· · 题解

提供一个线性做法。

我们无非是要计算

\begin{aligned} &\quad\; \sum_{i=1}^N A_i \sum_{j=1}^K \binom{i-1-(j-1)(D-1)}{j-1} \binom{N-i-(K-j)(D-1)}{K-j} \\ &= \sum_{i=1}^N A_i \sum_{j=1}^K \left([x^{i-1}] \frac{x^{(j-1)D}}{(1-x)^j}\right) \left([x^{N-i}] \frac{x^{(K-j)D}}{(1-x)^{K-j+1}}\right) \end{aligned}

不妨设置哑元 t，令 t^i 代替 A_i，则我们只需要计算

\begin{aligned} &\quad\; \sum_{i=1}^N t^i \sum_{j=1}^K \left([x^{i-1}] \frac{x^{(j-1)D}}{(1-x)^j}\right) \left([x^{N-i}] \frac{x^{(K-j)D}}{(1-x)^{K-j+1}}\right) \\ &= t \sum_{i=1}^N \sum_{j=1}^K \left([x^{i-1}] \frac{(xt)^{(j-1)D}}{(1-xt)^j}\right) \left([x^{N-i}] \frac{x^{(K-j)D}}{(1-x)^{K-j+1}}\right) \\ &= t \sum_{j=1}^K \sum_{i=0}^{N-1} \left([x^i] \frac{(xt)^{(j-1)D}}{(1-xt)^j}\right) \left([x^{N-1-i}] \frac{x^{(K-j)D}}{(1-x)^{K-j+1}}\right) \\ &= [x^{N-1}] t \sum_{j=1}^K \frac{(xt)^{(j-1)D}}{(1-xt)^j}\frac{x^{(K-j)D}}{(1-x)^{K-j+1}} \\ &= [x^{N-1}] \frac{tx^{(K-1)D}}{(1-xt)(1-x)^K} \sum_{j=0}^{K-1} \frac{t^{jD}(1-x)^j}{(1-xt)^j} \\ &= [x^{N-1-(K-1)D}] \frac t{(1-xt)(1-x)^K} \frac{1-t^{KD}(1-x)^K(1-xt)^{-K}}{1-t^D(1-x)(1-xt)^{-1}} \\ &= [x^{N-1-(K-1)D}] \frac t{(1-t^D)(1-x)^K} \frac{1-t^{KD}(1-x)^K(1-xt)^{-K}}{1-x\frac{t-t^D}{1-t^D}} \\ &= [x^{N-1-(K-1)D}] \frac t{1-t^D}\left(\frac1{(1-x)^K\left(1-x\frac{t-t^D}{1-t^D}\right)} - \frac{t^{KD}}{(1-xt)^K\left(1-x\frac{t-t^D}{1-t^D}\right)}\right) \\ \end{aligned}

注意后一部分在提取 [x^{N-1-(K-1)D}] 之后最低项是 t^{N+D}，因此事实上并没有贡献。

那么我们主要需要解决给定一个稀疏分式 u(t)=\frac{t-t^D}{1-t^D}，求解

[x^n] \frac1{(1-x)^k(1-xu)} = \sum_{j=0}^n \binom{n-j+k-1}{k-1} u^j

这自然关于 u D-Finite，因此也关于 t D-Finite，故可以做到 O(N)。

提交记录。