本文作于 2023 年 4 月。

作为一道生成函数的练习题。

不用生成函数推了好久还是错的。

以后遇到这类递推关系绝对首选 GF（能力范围内）。

简单观察不难发现，如果 \(m<n\)，那么无解。如果 \(m=n\)，那么只能是连续的 \(n\) 个01。

考虑 \(m>n\) 的情况，不难发现任何一个合法串都可以在一个初始串——连续的 \(n\) 个01中插入 \(m-n\) 个 \(0\) 得到。

如果将每一对01看作相对封闭的块，那么往块内放不同个 \(0\) 就能得到不同的串。先观察第一块内的情况，如图是 \(n-m=3\) 时，第一块的 Trie 树。

由于1后面必然是0，所以用数对 \((n,m)\) 表示从当前节点往下，还剩 \(n\) 个1，\(m\) 个0的话，每一个1后面的0都对应着 \((n-1,m-k)\)，\(k \in [1,n-m+1]\)。

划分子问题了。

于是乎设 \(f(n,m)\) 表示从这个0开始，后面还有 \(n\) 个1，\(m\) 个0，还需要的节点数。

\[ f(n,m) = \sum_{k \in [1,n-m+1]} \Big(f(n-1,m-k)+2\Big) \]

其中当 \(n=1\) 时，所有0必须都塞进第一块，于是 \(f(1,0)=0\)，\(f(1,m)=m+1\)。

考虑解这个递推关系。

设 \(f\) 的 \(OGF\) 为 \(F_n(x)\)，那么

\[ F_1(x) = 2x+3x^2 + 4x^3 + \cdots = \frac{1}{(1-x)^2} - 1 = \frac{x(2-x)}{(1-x)^2} \]

根据那个递推式得到，\(F_{n-1} \rightarrow F_n\) 是让所有满足 \(m \ge n-1\) 的 \(x_m\) 加上 \(2\) 然后再右移一位（原先 \(m\) 个1对应着新的 \(m+1\) 个），最后做前缀和（这个说法不严谨，加上了0的数量少于1的数量的方案，尽管他们都是 \(0\)）。

\[ F_n(x) = \Big(F_{n-1}(x) + \frac{2x^{n-1}}{1-x}\Big) \frac{x}{1-x} \]

又得到了一个递推式。

设 \(G_n(x) = \frac{F_n(x)}{x^n}\)，那么

\[ G_n(x) = \Big(G_{n-1}(x) + \frac{2}{1-x}\Big) \frac{1}{1-x} \]

由于我们知道首项 \(G_1(x)\) 的封闭形式 \(\frac{2-x}{(1-x)^2}\)，所以有一种套路的方法。

考虑让左边变成 \(G_n(x) + \Delta\)，满足右边是 \(\Big(G_{n-1}(x)+\Delta\Big) \frac{1}{1-x}\)。得到 \[ \frac{1}{1-x} \Delta - \Delta = \frac{2}{(1-x)^2} \]

解得 \(\Delta = \frac{2}{x(1-x)}\)

因此

\[ G_n(x) + \frac{2}{x(1-x)} = \Big(G_{n-1}(x) + \frac{2}{x(1-x)} \Big) \frac{1}{1-x} \]

代入 \(G_1=\frac{2-x}{(1-x)^2}\)

\[ G_n(x) + \frac{2}{x(1-x)} = \Big(G_1(x) + \frac{2}{x(1-x)} \Big) \frac{1}{(1-x)^{n-1}} \]

\[ G_n(x) + \frac{2}{x(1-x)} = \Big(\frac{2-x}{(1-x)^2} + \frac{2}{x(1-x)} \Big) \frac{1}{(1-x)^{n-1}} \]

这时候就能化简得到

\[ G_n(x) = \frac{2-x^2}{x(1-x)^{n+1}}-\frac{2}{x(1-x)} \]

从而

\[ F_n(x)=x^nG_n(x) = x^{n-1}\Big( \frac{2-x^2}{(1-x)^{n+1}}-\frac{2}{(1-x)} \Big) \]

然后愉快地展开

\[ f(n,m)=[x^m]F_n(x) = [x^{m-n+1}]G_n(x) \]

\[ [x^{m-n+1}]G_n(x) = [x^{m-n+1}] \left( 2\sum_{k=0}^{\infty} \binom{n+k}{k}x^k - x^2\sum_{k=0}^{\infty}\binom{n+k}{k}x^k - \sum_{k=0}^{\infty} 2x^k \right) \]

\[ [x^{m-n+1}]G_n(x) = [x^{m-n+1}] \left( \sum_{k=0}^{\infty} 2\binom{n+k}{k}x^k - \sum_{k=2}^{\infty}\binom{n+k-2}{k-2}x^k - \sum_{k=0}^{\infty} 2x^k \right) \]

\[ [x^{m-n+1}]G_n(x) = 2\binom{m+1}{n} - \binom{m-1}{n} - 2 \]

需要Lucas，然后求那个质数阶乘的逆元可以用威尔逊定理

\[ (p-1)! \equiv -1 \pmod p \] 结束。