P7386 题解

· · 题解

「EZEC-6」0-1 Trie

现在 tlx 有 n 个 \mathbf{1} 和 m 个 \mathbf{0}，你需要把它们排列，但要保证任意的 \mathbf{1} 互不相邻且第一个位置是 \mathbf{0}、最后一个位置是 \mathbf{1}，现在把所有可以构造出的串放到一棵 0-1 Trie 上，需要多少个节点？

注意：节点计数时，不计算最开始的空节点，只计算代表“ \mathbf{0} ”、“ \mathbf{1} ”的节点。

T\le 2\times 10^6,n,m\le 5\times 10^{18}

一道有一定难度的题，大概想了一个小时（还是太菜了

个人的做法比较愚笨复杂，其他题解可能有更加优秀的解法。

保证任意两个 1 互不相邻这个条件比较阴间，尝试将一个 1 强制与一个 0 捆绑起来，形成 01。

设 F_{x,y} 为有 x 个连续的 01，y 个单独的 0 的字典树节点数。

考虑这个字典树根节点的左右子树，如图所示：

图中用红色圈起的是有 x 个连续的 01，y 个单独的 0 的字典树。

它的左儿子这边，也就是绿色圈起的，是去掉一个 01 以后的字典树。

而右儿子这边，是去掉一个 0 之后的字典树。

整个红圈里的字典树就相当于绿圈里的加上蓝圈里的再加上两个节点。

于是可以得到 F_{x,y}=F_{x-1,y}+F_{x,y-1}+2,(x>1,y \ge 1) 的递推关系。

其中边界条件为 F_{1,y}=y+2,F_{x,0}=2x。

因为此时所有的节点形成了一条链，节点数就是链长。

（F_{1,y}=y 是因为题目里写了最后一个位置是 1，所以至少有一个连续的 01）。

然后整个 F 大概是这样的：

 列0  列1 列2 列3  列4
1: 2   3   4   5   6 
2: 4   9  15  22  30
3: 6  17  34  58  90
4: 8  27  63 123 215

除了第一行，都满足 F_{x,y}=F_{x-1,y}+F_{x,y-1}+2。

这样，我们总能够将 F_{n,m} 表示为 \sum k_j \times F_{1,j} + k_0\times 2 这样的形式。

对于 n>1， k_j 的系数相当于在网格图中从 (2,j) 走到 (n,m) 路径数（只能向右或者向下）。

而接下来要解决的就是 $k_0$ 的问题了。 这个 $k_0$ 相当于从 $\forall i\ge 2,j\ge 0$ $(i,j)$ 到 $(n,m)$ 的路径数量之和。 $k_0=\sum_{i=2}^n\sum_{j=0}^m \binom{n+m-i-j}{n-i}

根据上指标求和的式子，可以得到

k_0=\sum_{i=2}^n \binom{n+m-i+1}{n-i+1}=\sum_{i=2}^n\binom{n+m-i+1}{m}=(\sum_{i=2}^{n+1}\binom{n+m-i+1}{m})-1

再用一次上指标求和，得到

k_0=\binom{n+m}{m+1}-1

加上前面的这些式子，暴力求是单次 O(m) 的。

回来解决前面的这些式子。

\sum_{j=0}^mk_j\times F_{1,j}=\sum_{j=0}^m(j+2)\times \binom{n+m-j-2}{n-2} =\sum_{j=0}^m (m-j+2)\times \binom{n+j-2}{n-2} $=(\sum_{k=1}^{m+1}\sum_{j=0}^{k-1 }\binom{n+j-2}{n-2})+\binom{n+m-1}{n-1}$ 上指标求和。 $=(\sum_{k=1}^{m+1}\binom{n+k-2}{n-1})+\binom{n+m-1}{n-1}$ 再次上指标求和。 $=\binom{n+m}{n}+\binom{n+m-1}{n-1}

将式子整理一下

得到总的式子：

F_{n,m}=\binom{n+m}{n}+\binom{n+m-1}{n-1}+2\times \binom{n+m}{m+1}-2

已经可以求值了，不过如果你要精益求精的话，还可以继续化简，这一步不难（读者自证

最终式子为 2\times \binom{n+m+1}{n}-\binom{n+m-1}{n}-2，这样就可以只求两次组合数了。