[题解] [EZEC-6] 0-1 Trie

问所有由 $n$ 个 $1$ $m$ 个 $0$ 组成且不存在相邻 $1$ 的 $01$ 串构成的 Trie 的边数。

$T$ 组数据，$T\le2\cdot 10^6$，$1\le n,m\le 5\cdot 10^{18}$

题目链接

第一次让我感到屈辱的推式…

有个显然的观察，答案等于 $(n+m)$ 乘上合法串的个数，再减去所有串按字典序排序后相邻两个的 $LCP$。如果你走 dp 那你就会沦为和我给同学做题时一样的心理崩溃，于是我们考虑组合。

不难发现由于我们按字典序排序，每种 $LCP$ 只会被计算一次。我们只需要考虑哪些 $LCP$ 是合法的并把它们的长度加起来即可。首先不难发现 $n$ 个 $1$ $m$ 个 $0$ 形成题目中要求串的方案是 $\binom{m-1}{n-1}$（隔板法），然后能形成合法串的充要条件显然是 $n\le m$。

于是我们开始枚举 $LCP$ 长度，再枚举其中有多少个 $1$。不难注意到相邻的两个字符串必然是这样的形式：

$$ \text{枚举的前缀}+\underline 0\cdots\\ \text{枚举的前缀}+\underline 1\cdots $$

否则 $LCP$ 就可以更长。于是 $LCP$ 末尾必然是 $0$。然后考虑上面合法串的充要条件，假设 $LCP$ 长度为 $i$ 且有 $j$ 个 $1$，我们得到下面的条件：

$$ i-j\ge j+1\\ (n+m-i)-(n-j)\ge n-j\\ (n+m-i-1)-(n-j-1)\ge n-j-1 $$

即 $2j+1\le i\le m-n+2j$。由于除去 $LCP$ 后面的部分至少有两个 $1$（如果只有一个 $1$，也就是 $i=n-m+1$，则上面列出的第一个字符串不合法）所以 $j$ 最大为 $n-2$。，于是我们得到相邻 $LCP$ 长度的和应为：

$$ \sum_{j=0}^{n-2}\sum_{i=2j+1}^{m-n+2j}i\binom{i-j-1}j $$

于是开始无脑推式子。

$$ \begin{aligned} &=\sum_{j=0}^{n-2}\left(\left(\sum_{i=2j+1}^{m-n+2j}(i-j)\binom{i-j-1}j\right)+j\sum_{i=2j+1}^{m-n+2j}\binom{i-j-1}j\right)\\ &=\sum_{j=0}^{n-2}\left(\left(\sum_{i=2j+1}^{m-n+2j}(j+1)\binom{i-j}{j+1}\right)+j\binom{m-n+j}{j+1}\right)\\ &=\sum_{j=0}^{n-2}(j+1)\binom{m-n+j+1}{j+2}+j\binom{m-n+j}{j+1}\\ &=(n-1)\binom{m-1}n+2\sum_{j=1}^{n-2}j\binom{m-n+j}{j+1} \end{aligned} $$

梅 开 二 度

把右边那个东西拿过来

$$ \begin{aligned} &\sum_{j=0}^{n-2}j\binom{m-n+j}{j+1}\\ =&\left(\sum_{j=0}^{n-2}(m-n+j+1)\binom{m-n+j}{m-n-1}\right)-(m-n+1)\sum_{j=0}^{n-2}\binom{m-n+j}{m-n-1}\\ =&\left(\sum_{j=0}^{n-2}(m-n)\binom{m-n+j+1}{m-n}\right)-(m-n+1)\left(\binom{m-1}{m-n}-1\right)\\ =&(m-n)\left(\binom m{m-n+1}-1\right)-(m-n+1)\left(\binom{m-1}{m-n}-1\right)\\ =&(m-n)\binom m{m-n+1}-(m-n+1)\binom{m-1}{m-n}+1 \end{aligned} $$

综合一下我们得到

$$ \begin{aligned} Ans=&(n+m)\binom{m-1}{n-1}-(n-1)\binom{m-1}{n}-\\ &2(m-n)\binom m{m-n+1}+2(m-n+1)\binom{m-1}{m-n}-2 \end{aligned} $$

已经可以 $O(1)$ 求了，但为什么你的式子那么丑啊！！！！

出于莫名奇妙的执着，我们化简一下

$$ \begin{aligned} Ans=&(3m-n+2)\binom{m-1}{n-1}-(n-1)\binom{m-1}{n}-\\ &2(m-n)\binom m{n-1}-2\\ =&2\binom m{n-1}+\binom{m-1}n+2\binom{m-1}{n-1}-2\\ =&\binom{m-1}{n-1}+\binom m{n-1}+\binom{m+1}n-2\\ =&2\binom{m+1}n-\binom{m-1}n-2 \end{aligned} $$

代码只有 Lucas，想必不用贴了。

/ Peace Out /