题解【SOI Round 1 D】觅

### 算法一 考虑dp，$f_{i,j}$表示从$(0,0)$走到$(i,j)$的方案数，那么有 $$ f_{i,j}=\begin{cases}1&ij=0\\f_{i-1,j}+f_{i,j-1}+f_{i-1,j-1}&ij\neq 0\end{cases} $$ 复杂度$O(n^2)$，期望得分$30$分 ### 算法二 考虑没有斜步怎么做，这时的方案数即$\binom{2n}{n}$，因为向上和向右一共要走$2n$步， 其中向上向右各$n$步.从这$2n$步里选出$n$步向上即可. 现在考虑斜步，假设有$k$个斜步，那么向上的步和向右的步都还剩$n-k$个，再加上斜步一共有$2n-k$步，从$2n-k$步里选出$k$个斜步，再从剩下$2n-2k$步里选出$n-k$个向上的步，方案数为 $$ \binom{2n-k}{k}\binom{2(n-k)}{n-k} $$ 枚举走了几个斜步，从$(0,0)$走到$(n,n)$的方案数即 $$ \sum_{k=0}^n\binom{2n-k}{k}\binom{2(n-k)}{n-k} $$ 计算单个$n$的复杂度是$O(n)$，总复杂度$O(n^2)$，期望得分$30$分. ### 算法三 考虑化一下算法二中的式子. $$ \begin{aligned}&\sum_{k=0}^n\binom{2n-k}{k}\binom{2(n-k)}{n-k}\\=&\sum_{k=0}^n\binom{n+k}{n-k}\binom{2k}{k}\\=&\sum_{k=0}^n\binom{n+k}{2k}\binom{2k}{k}\\=&\sum_{k=0}^n\binom{n+k}{k}\binom{n}{k}\\=&\sum_{k=0}^n\binom{n}{k}\sum_{j}\binom{n}{j}\binom{k}{k-j}\\=&\sum_{j}\binom{n}{j}\sum_{k=0}^n\binom{n}{k}\binom{k}{j}\\=&\sum_j\binom{n}{j}\binom{n}{j}\sum_{k=0}^n\binom{n-j}{k-j}\\=&\sum_{j}\binom{n}{j}^22^{n-j}\end{aligned} $$ 可以使用$NTT$优化，复杂度$O(n\log n)$，期望得分$60$分 ### 算法四 考虑数列$f_n$表示从$(0,0)$走到$(n,n)$的方案数，$g_n$表示从$(0,0)$走到$(n,n)$且不越过(可以碰到)对角线的方案数，考虑第一步有三种走法: 1. 走一个斜步，此时还需要从$(1,1)$走到$(n,n)$，方案数是$f_{n-1}$ 2. 向右走一步，然后枚举第一次碰到对角线的位置$(k,k)$，因为是第一次碰到，所以碰到对角线的这一步一定是向上走的，所以相当于从$(1,0)$走到$(k,k-1)$并且中间任何一个位置$(i,j)$都满足$i>j$，向下平移一格就是从$(0,0)$走到$(k-1,k-1)$且不越过对角线，方案数是$g_{k-1}$;还需要从$(k,k)$走到$(n,n)$，方案数是$f_{n-k}$，总的方案数就是 $$ \sum_{k=1}^n g_{k-1}f_{n-k}=\sum_{k=0}^{n-1}g_{n-1-k}f_k $$ 3. 向上走一步，是向右走的对称情况，方案数同上 所以有 $$ f_n=f_{n-1}+2\sum_{k=0}^ng_{n-1-k}f_{k} $$ 以及显然的 $$ f_0=1 $$ 设$f$的生成函数是$F(x)$，$g$的生成函数是$G(x)$，那么有 $$ \begin{aligned}F(x)&=\sum_{i\geq 0}f_ix^i\\&=f_0+\sum_{i\geq 1}x^i\left(f_{i-1}+2\sum_{k=0}^{i-1}f_kg_{i-1-k}\right)\\&=1+xF(x)+2xF(x)G(x)\end{aligned} $$ 解方程就得到 $$ F(x)=\frac{1}{1-x-2xG(x)} $$ 现在来考虑$g$，根据和之前差不多的分析方法可以得到 $$ g_n=g_{n-1}+\sum_{k=0}^{n-1}g_kg_{n-1-k},g_0=1 $$ 所以对$G(x)$就有 $$ \begin{aligned}G(x)&=\sum_{i\geq 0}g_ix^i\\&=g_0+\sum_{i\geq 1}x^i\left(g_{i-1}+\sum_{k=0}^{i-1}g_kg_{i-1-k}\right)\\&=1+xG(x)+xG(x)^2\end{aligned} $$ 解方程就得到 $$ G(x)=\frac{1-x\pm\sqrt{x^2-6x+1}}{2x} $$ 其中有一个根需要舍去，带入$x=0$检验: $$ \lim_{x\to 0}\frac{1-x\pm\sqrt{x^2-6x+1}}{2x}=\lim_{x\to 0}\frac{2}{1-x\mp\sqrt{x^2-6x+1}}=\frac{2}{1\mp 1} $$ 发现根号前面取加号会使得这个极限是$+\infty$而取减号是$1$，因为$g_0=1$所以我们需要取减号.于是 $$ G(x)=\frac{1-x-\sqrt{x^2-6x+1}}{2x} $$ 带入到$F(x)$的式子里就得到 $$ F(x)=\frac{1}{\sqrt{x^2-6x+1}} $$ 把这个东西用多项式技术展开一下就能得到$f$，复杂度$O(n\log n)$，期望得分$80$分 ### 算法五 利用$f$的生成函数可以得到一些有用的东西.在等式两边求导得到 $$ F'(x)=-\frac{2x-6}{2(x^2-6x+1)\sqrt{x^2-6x+1}}=\frac{3-x}{x^2-6x+1}F(x) $$ 也就是 $$ (x^2-6x+1)F'(x)-(3-x)F(x)=0 $$ 展开$F(x)$以及$F'(x)$就得到 $$ \sum_{i\geq 0}(x^2-6x+1)if_ix^{i-1}-\sum_{i\geq 0}(3-x)f_ix^i=0 $$ 整理一下得到 $$ \sum_{i\geq 0}(i+1)f_ix^{i+1}-\sum_{i\geq 0}(6i+3)f_ix^i+\sum_{i\geq 0}if_ix^{i-1}=0 $$ 因为等式右边是$0$，所以对任意$i\geq 0$有$x^{i+1}$项的系数为$0$，所以有 $$ (i+1)f_{i}-3(2i+3)f_{i+1}+(i+2)f_{i+2}=0 $$ 即 $$ (i+2)f_{i+2}=3(2i+3)f_{i+1}-(i+1)f_i $$ 按照这个式子递推，复杂度$O(n)$，期望得分$100$分+神秘奖励 ### 算法五EX 某天去UOJ裙问到的一个更强的结论. 设 $$ F(x)=G(x)^k,k\in \mathbb{R},G(x)\text{是多项式函数} $$ 两边求导得 $$ \begin{array}{ccc}F'(x)=kG(x)^{k-1}G'(x)\\\\F'(x)G(x)=kG(x)^kG'(x)=kF(x)G'(x)\end{array} $$ 因为$G'(x)$一定也是多项式函数，所以直接把两边展开就可以得到一个递推关系. ### ~~算法六~~ ~~使用算法一进行打表，将打出来的表丢到OEIS上，找到这个数列的递推公式进行计算，复杂度O(n)，期望得分100分但没有神秘奖励~~ **20200913upd** 看到粉兔在群里问了一下这个东西，发现 EI 队长给出了代数推法 从算法三入手，搞出OGF $$ \begin{aligned} &\sum_{n\geq 0}z^n\sum_{k}\binom{n+k}{n-k}\binom{2k}{k}\\ =&\sum_k\binom{2k}{k}\sum_{n\geq 0}z^n\binom{n+k}{n-k}\\ =&\sum_k\binom{2k}{k}z^k\sum_{n\geq 0}z^n\binom{n+2k}{n}\\ =&\sum_k\binom{2k}{k}z^k\frac{1}{(1-z)^{2k+1}}\\ =&\frac{1}{1-z}\sum_{k\geq 0}\binom{2k}{k}\left(\frac{z}{(1-z)^2}\right)^k\\ =&\frac{1}{1-z}\left(\sqrt{1-\frac{4z}{(1-z)^2}}\right)^{-1}\\ =&\frac{1}{\sqrt{z^2-6z+1}} \end{aligned} $$