双射是什么，和我的 Kernel Method 说去吧

· · 题解

首先我们对整个平面做线性变换：(x,y) \to (x,x-y)。这样就变成了从 (0,0) 移动到 (n,0) 且不越过 y=0 这条线，方便我们描述一些。

现在就有一个简单的 DP，给定 f_0(z)=1，以及递推式

f_k(z)=\frac{1}{1-z}\sum_{i=0}^k a_i (f_{k-i}(1)-z^i f_{k-i}(z))

（含义：如果 x 选择走 a_i 长度，那么第二维可以走到 y+a_i-1 以内的任意自然数）

尝试求出 f_n(0)。建立二元 GF 就有方程

(1-z)F(z,t)=A(t) F(1,t)- A(tz)F(z,t)+1-z

由此也能得到

F(z,t) = \frac{A(t)F(1,t)+1-z}{1-z+A(tz)}

而我们知道 [z^{n+1}]F(z,t)\equiv 0 \pmod{t^{n+1}}（没法走到这么高），根据这一点可以解出 F(1,t)。设

g_k(t)=[z^k] \frac{1}{1-z+A(tz)}

则

F(0,t)\equiv A(t)F(1,t)+1 \equiv \frac{g_n(t)}{g_{n+1}(t)} \pmod{t^{n+1}}

那么问题就变为如何快速计算 g_k(t) 了...吗？直接计算 g_k(t) 可能比较困难，如果能直接计算两项之比就好了。大家一定知道 Fibonacci 数相邻两项之比的极限吧：

\lim_{n \to \infty} \frac{f_n}{f_{n+1}}=\frac{\sqrt 5 - 1}{2}

它等于 f_n 递推式中，模长最大的特征根的倒数。显然 g_n(t)/g_{n+1}(t) 的极限也是存在的，我们尝试用类似的方法处理。显然我们先验地知道这个极限的常数项为 1，且不存在负次项，这将给后续推导提供重要帮助。

考虑到特征方程 z^n(1-z^{-1}+A(t/z)) 有多达 n 个根难以处理，但既然 g_n(t)/g_{n+1}(t) 的极限已经确定了最低非零项，那么我们只需要找出特征方程中也满足相同性质的那个根即可。

也就是说，我们要找一个形式幂级数 F(t)，满足 F(0)=1，且

F(t)^n(1-1/F(t)+A(t/F(t)))=0

（很幸运，满足条件的 F(t) 是唯一的）

那么答案即为 [t^n]1/F(t)。
稍微化简一下，设 G(t)=1/F(t)，则方程变为

1-G(t)+A(t G(t))=0 t = tG(t) - t A(t G(t))

所求的答案也变为 [t^{n+1}] tG(t)。令 H(t) 为 tG(t) 的复合逆，则 H(t)=t-H(t)A(t)，答案也就是

[t^{n+1}] tG(t)=\frac{1}{n+1}[x^n] \left( \frac{t}{H(t)}\right)^{n+1}=\frac{1}{n+1}[t^n](1+A(t))^{n+1}

完全胜利！