作为一道生成函数的练习题。
不用生成函数推了好久还是错的。
以后遇到这类递推关系绝对首选 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$ 的 $\text{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}$
解得 $\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
$$
结束