题解 【SOI Round 1 C】寻

### 算法一 考虑dp，$f_{i,j,k}$表示从$(0,0)$走到$(i,j)$，用了$k$个斜步的方案数，那么有 $$ \begin{array}{ccc}f_{i,0,0}=f_{0,i,0}=1\\\\f_{i,j,0}=f_{i-1,j,0}+f_{i,j-1,0}(i,j>0)\\\\f_{i,j,k}=f_{i-1,j,k}+f_{i,j-1,k}+f_{i-1,j-1,k-1}(i,j,k>0)\end{array} $$ 复杂度$O(n^2m)$，期望得分$20$分 ### 算法二 考虑没有斜步怎么做，这时的方案数即$\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}^{m}\binom{2n-k}{k}\binom{2(n-k)}{n-k} $$ 计算单个$n$的复杂度是$O(m)$，总复杂度$O(nm)$，期望得分$50$分. ### 算法三 考虑化一下算法二中的式子. $$ \begin{aligned}&\sum_{k=0}^m\binom{2n-k}{k}\binom{2(n-k)}{n-k}\\=&\sum_{k=n-m}^n\binom{n+k}{n-k}\binom{2k}{k}\\=&\sum_{k=n-m}^n\binom{n+k}{2k}\binom{2k}{k}\\=&\sum_{k=n-m}^n\binom{n+k}{k}\binom{n}{k}\\=&\sum_{k=n-m}^n\binom{n}{k}\sum_{j}\binom{n}{j}\binom{k}{k-j}\\=&\sum_{j}\binom{n}{j}\sum_{k=n-m}^n\binom{n}{k}\binom{k}{j}\\=&\sum_j\binom{n}{j}\binom{n}{j}\sum_{k=n-m}^n\binom{n-j}{k-j}\\=&\sum_{j}\binom{n}{j}^2\sum_{k=n-m-j}^{n-j}\binom{n-j}{k}\end{aligned} $$ 发现后面的 $$ \sum_{k=n-m-j}^{n-j}\binom{n-j}{k} $$ 是一个只和$n-j$与$m$有关的东西.如果我们处理出这个东西就可以使用$NTT$优化到$O(n\log n)$. 考虑 $$ S(n)=\sum_{k=n-m}^n\binom{n}{k} $$ 从$n$转移到$n+1$: $$ \begin{aligned}S(n+1)&=\sum_{k=n-m+1}^{n+1}\binom{n+1}{k}\\&=\sum_{k=n-m+1}^{n+1}\binom{n}{k}+\binom{n}{k-1}\\&=2\sum_{k=n-m}^n\binom{n}{k}+\binom{n}{n+1}-\binom{n}{n-m}\\&=2S(n)-\binom{n}{n-m}\end{aligned} $$ 于是可以递推处理出来$S$. 复杂度$O(n\log n)$，期望得分$100$分.