题解：P7386 「EZEC-6」0-1 Trie

Elairin176 · 2025-08-13 22:43:12 · 题解

Link

前言

若无特别说明，文中所有数字均为正整数。

题意

给定 n 个 1 和 m 个 0，要求用它们组成一个 n+m 的串，并满足：

开头是 0，结尾是 1。
两个 1 不能相邻。

将所有合法的串放到一棵 Trie 上，求这棵 Trie 上的结点数。（除去空的根结点，且字符存在结点上）
模 18888913（质数），1\le n,m\le5\times10^{18}，多组询问，1\le T\le2\times10^6，输出所有结果的异或值。

解法

1 不能相邻这个要求很难受。所以我们不妨把 1 和 0 合并起来，这样就不用考虑相邻的问题了。
题面有个要求：开头必须是 0，最后必须是 1，所以我们考虑将 10 合并。 ::::info[为何不考虑 01 合并？] 如果我们使用了 01 合并，那么串如果形如 01... 将不方便处理，而且无法处理与最后的 1 相邻的情况。简单地说就是 10 合并更方便。 ::::
我们把开头的 0 和最后的 1 独立出来考虑：开头的 0 显然只占了一个结点，所以对答案的贡献仅有 1，而计算最后的 1 用了多少结点实际上就是在计算能生成多少种串。
计算串的数量我们需要先知道有多少 10 和单独的 0（下文将简称为 0）。因为去掉了开头结尾，所以还剩下 n-1 个 1 和 m-1 个 0，因为我们合并了 10，所以 10 的个数为 n-1 个，此时还会被拿去 n-1 个额外的 0，所以实际上 0 的数量有 m-n 个。
::::warning[一个小细节] 根据上面的结果，应有 m-n\ge0，即 m\ge n，否则无解。 :::: 那么串的种类数就显然是 \binom{m-1}{n-1} 了。我们将 10 和 0 都看成是 1 个元素就容易推得上式。
所以结尾 1 的数量是 \binom{m-1}{n-1}。
接下来我们就要考虑中间产生了多少贡献。
我们先考虑用 dp 的方式解决。
设 f_{i,j} 为中间段有 i 个 0，j 个 10 时所产生的贡献，此时我们令 Trie 上存在一个父亲结点容纳下面的点。我们容易得出以下递推：

f_{i,j}=\begin{cases}i&j=0\\2j&i=0\\f_{i-1,j}+f_{i,j-1}+3&\texttt{otherwise.}\end{cases}

这里一般递推的情况中，对两边进行了分类讨论。若此时使用 0，那么贡献为 f_{i-1,j}+1；若使用 10，则会贡献 f_{i,j-1}+2，两边求和就是递推式。
一般地，这种递推都可以写成组合数的和。现在我以这个题为例讲解。
对于任意的 f_{i,j}，我们把结果分为三个部分:

递推过程中积累的 3 之和。

容易发现第二部分的贡献就是第一部分贡献的 2 倍，所以这里只讲解第一部分。
为了便于叙述，先给出一个定义：设一个数列满足各项均为同一个数，则称其为 0 阶等差数列；若一个数列满足其差分数列为 n-1 阶等差数列，则原序列为 n 阶等差数列。特别地，若一个数列各项均为 1，则称其为 0 阶基等差数列，若对一个 n 阶等差数列进行 n 阶差分后可得到 0 阶基等差数列，则称原数列为 n 阶基等差数列。
根据定义，我们容易得出 n 阶基等差数列的各项其实就是对 n-1 阶基等差数列的对应项求和。 ::::info[关于差分] 设一个数列 \{a_n\} 的差分数列 \{b_n\} 为 \forall i\in[1,n] 有 b_i=a_i-a_{i-1}，特别规定 a_0=0。

:::: 回到正题。根据 $f_{i,j}$ 的一般递推式，$j=0$ 处的贡献应为 $f_{i-1,j}$ 和 $f_{i,j-1}$ 时 $j=0$ 处的贡献之和。我们考察 $f_{i-1,j}$，展开至 $i=0$ 时容易发现 $f_{i,j}$ 接受的 $j=0$ 处的贡献就等于 $f_{x,j-1}(1\le x\le i)$ 的 $j=0$ 处的贡献之和。我们观察到 $j=0$ 处各项实际上就是 $0$ 阶基等差数列的对应各项和，归纳易得 $f_{i,j}$ 处 $j=0$ 的贡献就是 $j$ 阶基等差数列的前 $i$ 项和，或者说，就是 $j+1$ 阶基等差数列的第 $i$ 项。那么怎么求呢？我们考虑**组合意义**。我们令 $g_{i,j}$ 表示 $i$ 阶基等差数列第 $j$ 项，那么有： $g_{i,j}=\begin{cases}0&j=0\\1&i=0\\\sum\limits_{p=1}^j g_{i-1,p}&\texttt{otherwise.}\end{cases}

我们注意到：令 g_{i,j} 表示满足 x_1+x_2+\cdots+x_j=i 且 \forall k\in[1,j] 有 x_k 为非负整数的有序 j 元组 (x_1,x_2,\dots,x_j) 的数量也是成立的！
::::info[为何这是成立的？] 对于边界情况，显然是对的。
一般的情况中，我们注意到 g_{i,j}=g_{i,j-1}+g_{i-1,j}。而对于我们转化后的组合意义，这恰是其转移式。具体地：

对于有序 j 元组，我们考虑 x_j 的值。
若 x_j=0，则有 \sum\limits_{p=1}^{j-1}x_p=i，故产生 g_{i,j-1} 的贡献。
若 x_j>0，则我们考虑有序 j 元组 (x_1,x_2,\dots,x_j-1)，我们只需统计它的数量。贡献就是 g_{i-1,j}。
两者相加就是总数。 :::: 那么我们考虑求解转化后的组合意义。这是一个经典的问题，我们可以考虑“插板法”，容易得出 g_{i,j}=\binom{i+j-1}{j-1}。 ::::info[关于这个问题的推导] 我们将 i 分成 i 个 1 相加。那么 1 之间会产生 i-1 个“间隔”，在“间隔”中我们可以放“板”。一个“板”会将其所在的极大 1 块分为 2 份，即生成了两段 x 的和。
对于原问题，因为 x_p 可以取到 0 且要求有序，所以“板”可以插在第一个 1 的左侧或最后的 1 右侧（即开头结尾），这样就有了 i+1 个“间隔”。
同时，我们关注到多个“板”可以同时放在一个“间隔”中，表示 x 中存在一段 0，所以我们不妨考虑增加若干个“通配间隔”，用于容纳这些重复的“板”。因为“板”一共需要 j-1 个（拆成 j 段，即 j 个元），所以我们需要 j-2 个“通配间隔”，与原来的间隔合起来可得总共有 i+j-1 个“间隔”，那么答案就显而易见了：共 \binom{i+j-1}{j-1} 个放“板”的方式，也就是这么多组 x 的可行解。此时对于边界情况也是没问题的。 :::: 我们要求的是 g_{j+1,i}，带入得 \binom{i+j}{i-1}，这便是第一部分的贡献。
类似地，第二部分的贡献为 2\binom{i+j}{j-1}。
接下来我们考虑第三部分。我们设 f'_{n,m} 表示 f_{n,m} 所包含的 3 的贡献的总数。那么，我们容易得出递推式： f'_{i,j}=\begin{cases}0&i=0\lor j=0\\f'_{i-1,j}+f'_{i,j-1}+1&\texttt{otherwise.}\end{cases}

注：P\lor Q 表示 P 或 Q，即 P,Q 间至少有一个成立。

那么实际上 f_{i,j} 中 3 的贡献就是 3f'_{i,j}。
我们还是考虑赋予其组合意义。容易发现 f'_{i,j} 实际上就是从平面上任意的 (x,y)(1\le x\le i,1\le y\le j) 仅向右、向下走到 (i,j) 的不同路径数量。
::::info[关于这个组合意义的正确性] 这个组合意义正确性的证明是显然的，因为走一步到 (i,j) 只有两个方法：从 (i-1,j) 或 (i,j-1) 过来。所以将 f'_{i-1,j} 和 f'_{i,j-1} 相加。同时我们发现这么处理会漏掉 (i,j) 走到 (i,j) 本身的方案，所以加 1 即可。
::::
然后我们考虑翻转整个平面，使 (i,j) 变为 (1,1)，那么对应地，我们就要求从任意的 (x,y)(1\le x\le i,1\le y\le j) 仅向上、向左走到 (1,1) 的不同路径数量。容易得出为 \sum\limits_{p=1}^i\sum\limits_{q=1}^j\binom{p+q-2}{p-1}。
::::info[关于路径计数] 从 (x,y) 仅向上、向左走到 (1,1) 的方案计数我们可以考虑其每步的变化量。
容易发现其必向上 x-1 步，向左 y-1 步，不同的路径实际上是不同的变化量的组合。
那么此时其方案数就有 \binom{x+y-2}{x-1}。 :::: 我们把我们推出的求和式子带入递推式：

\begin{aligned}f'_{i,j}&=f'_{i-1,j}+f'_{i,j-1}+1\\&\Downarrow\\\sum\limits_{p=1}^i\sum\limits_{q=1}^j\binom{p+q-2}{p-1}&=\sum\limits_{p=1}^{i-1}\sum\limits_{q=1}^j\binom{p+q-2}{p-1}+\sum\limits_{p=1}^i\sum\limits_{q=1}^{j-1}\binom{p+q-2}{p-1}+1\\&=2\sum\limits_{p=1}^{i-1}\sum\limits_{q=1}^{j-1}\binom{p+q-2}{p-1}+\sum\limits_{p=1}^{i-1}\binom{p+j-2}{j-1}+\sum\limits_{q=1}^{j-1}\binom{q+i-2}{i-1}+1\\&\Downarrow\\\binom{i+j-2}{i-1}&=\sum\limits_{p=1}^{i-1}\sum\limits_{q=1}^{j-1}\binom{p+q-2}{p-1}+1\\&\Downarrow\\f'_{i-1,j-1}&=\binom{i+j-2}{i-1}-1\\&\Downarrow\\f'_{i,j}&=\binom{i+j}i-1\end{aligned}

那么我们容易得到 3 对 f_{i,j} 的贡献就是 3\binom{i+j}i-3，求和可得：

f_{i,j}=\binom{i+j}{i-1}+2\binom{i+j}{j-1}+3\binom{i+j}{j}-3

带入一开始的式子，则有：

\begin{aligned}1+\binom{m-1}{n-1}+f_{m-n,n-1}&=1+\binom{m-1}{n-1}+\binom{m-1}{n}+2\binom{m-1}{n-2}+3\binom{m-1}{n-1}-3\\&=4\binom{m-1}{n-1}+2\binom{m-1}{n-2}+\binom{m-1}n-2\end{aligned}

因为本题数据范围很大、模数很小，所以我们要使用 Lucas 定理辅助计算。
另外就是本题比较卡常，所以 cin 可能会被卡。
Record
Code：

//luogu paste jo5j6ogx
cst ll p=18888913;
int t;
ll n,m,fac[p+10],inv[p+10],ans,r;
il ll C(int n,int m){
    if(m<0||m>n) ret 0;
    ret fac[n]*inv[n-m]%p*inv[m]%p;
}
il ll Lucas(ll n,ll m){
    if(m<0||m>n) ret 0;
    if(n>p||m>p) ret C(n%p,m%p)*Lucas(n/p,m/p)%p;
    ret C(n,m);
}
int main(void){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    fac[0]=1;
    for(ll i=1;i<p;i++) fac[i]=fac[i-1]*i%p;
    inv[p-1]=pinv(fac[p-1],p);
    for(ll i=p-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%p;
    t=read<int>();
    while(t--){
        n=read<ll>();m=read<ll>();
        if(n>m) continue;
        ans=msub(madd(madd(4ll*Lucas(m-1,n-1)%p,2ll*Lucas(m-1,n-2)%p,p),Lucas(m-1,n),p),2,p);
        r^=ans;
    }
    write(r);
    ret 0;
}

后记

写得很详细呢，就当是给组合数学初学者的一份入门教程了。