专栏文章

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

EElairin176
P7386题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miocjbd5
此快照首次捕获于
2025/12/02 16:58
3 个月前
此快照最后确认于
2025/12/02 16:58
3 个月前
查看原文
Link

前言

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

题意

给定 nn 个 1 和 mm 个 0，要求用它们组成一个 n+mn+m 的串，并满足：
  • 开头是 0，结尾是 1。
  • 两个 1 不能相邻。
将所有合法的串放到一棵 Trie 上，求这棵 Trie 上的结点数。（除去空的根结点，且字符存在结点上）
模 1888891318888913（质数），1≤n,m≤5×10181\le n,m\le5\times10^{18}，多组询问，1≤T≤2×1061\le T\le2\times10^6，输出所有结果的异或值。

解法

1 不能相邻这个要求很难受。所以我们不妨把 1 和 0 合并起来，这样就不用考虑相邻的问题了。
题面有个要求：开头必须是 0，最后必须是 1，所以我们考虑将 10 合并。
为何不考虑 01 合并？
如果我们使用了 01 合并，那么串如果形如 01... 将不方便处理，而且无法处理与最后的 1 相邻的情况。 简单地说就是 10 合并更方便。
我们把开头的 0 和最后的 1 独立出来考虑：开头的 0 显然只占了一个结点，所以对答案的贡献仅有 11，而计算最后的 1 用了多少结点实际上就是在计算能生成多少种串。
计算串的数量我们需要先知道有多少 10 和单独的 0（下文将简称为 0）。因为去掉了开头结尾，所以还剩下 n−1n-1 个 1 和 m−1m-1 个 0，因为我们合并了 10，所以 10 的个数为 n−1n-1 个，此时还会被拿去 n−1n-1 个额外的 0，所以实际上 0 的数量有 m−nm-n 个。
一个小细节
根据上面的结果，应有 m−n≥0m-n\ge0，即 m≥nm\ge n，否则无解。
那么串的种类数就显然是 (m−1n−1)\binom{m-1}{n-1} 了。我们将 10 和 0 都看成是 11 个元素就容易推得上式。
所以结尾 1 的数量是 (m−1n−1)\binom{m-1}{n-1}。
接下来我们就要考虑中间产生了多少贡献。
我们先考虑用 dp 的方式解决。
设 fi,jf_{i,j} 为中间段有 ii 个 0，jj 个 10 时所产生的贡献，此时我们令 Trie 上存在一个父亲结点容纳下面的点。我们容易得出以下递推：
fi,j={ij=02ji=0fi−1,j+fi,j−1+3otherwise.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，那么贡献为 fi−1,j+1f_{i-1,j}+1；若使用 10，则会贡献 fi,j−1+2f_{i,j-1}+2，两边求和就是递推式。
一般地，这种递推都可以写成组合数的和。现在我以这个题为例讲解。
对于任意的 fi,jf_{i,j}，我们把结果分为三个部分:
  1. j=0j=0 处贡献的 ii 之和。
  2. i=0i=0 处贡献的 2j2j 之和。
  3. 递推过程中积累的 33 之和。
容易发现第二部分的贡献就是第一部分贡献的 22 倍，所以这里只讲解第一部分。
为了便于叙述，先给出一个定义：设一个数列满足各项均为同一个数，则称其为 00 阶等差数列；若一个数列满足其差分数列为 n−1n-1 阶等差数列，则原序列为 nn 阶等差数列。特别地，若一个数列各项均为 11，则称其为 00 阶基等差数列，若对一个 nn 阶等差数列进行 nn 阶差分后可得到 00 阶基等差数列，则称原数列为 nn 阶基等差数列。
根据定义，我们容易得出 nn 阶基等差数列的各项其实就是对 n−1n-1 阶基等差数列的对应项求和。
关于差分
设一个数列 {an}\{a_n\} 的差分数列 {bn}\{b_n\} 为 ∀i∈[1,n]\forall i\in[1,n] 有 bi=ai−ai−1b_i=a_i-a_{i-1}，特别规定 a0=0a_0=0。
nn 阶差分就是进行 nn 次差分操作。
回到正题。根据 fi,jf_{i,j} 的一般递推式，j=0j=0 处的贡献应为 fi−1,jf_{i-1,j} 和 fi,j−1f_{i,j-1} 时 j=0j=0 处的贡献之和。我们考察 fi−1,jf_{i-1,j}，展开至 i=0i=0 时容易发现 fi,jf_{i,j} 接受的 j=0j=0 处的贡献就等于 fx,j−1(1≤x≤i)f_{x,j-1}(1\le x\le i) 的 j=0j=0 处的贡献之和。我们观察到 j=0j=0 处各项实际上就是 00 阶基等差数列的对应各项和，归纳易得 fi,jf_{i,j} 处 j=0j=0 的贡献就是 jj 阶基等差数列的前 ii 项和，或者说，就是 j+1j+1 阶基等差数列的第 ii 项。
那么怎么求呢？我们考虑组合意义。
我们令 gi,jg_{i,j} 表示 ii 阶基等差数列第 jj 项，那么有：
gi,j={0j=01i=0∑p=1jgi−1,potherwise.g_{i,j}=\begin{cases}0&j=0\\1&i=0\\\sum\limits_{p=1}^j g_{i-1,p}&\texttt{otherwise.}\end{cases}
我们注意到：令 gi,jg_{i,j} 表示满足 x1+x2+⋯+xj=ix_1+x_2+\cdots+x_j=i 且 ∀k∈[1,j]\forall k\in[1,j] 有 xkx_k 为非负整数的有序 jj 元组 (x1,x2,…,xj)(x_1,x_2,\dots,x_j) 的数量也是成立的！
为何这是成立的？
对于边界情况，显然是对的。
一般的情况中，我们注意到 gi,j=gi,j−1+gi−1,jg_{i,j}=g_{i,j-1}+g_{i-1,j}。而对于我们转化后的组合意义，这恰是其转移式。具体地：
  • 对于有序 jj 元组，我们考虑 xjx_j 的值。
  • 若 xj=0x_j=0，则有 ∑p=1j−1xp=i\sum\limits_{p=1}^{j-1}x_p=i，故产生 gi,j−1g_{i,j-1} 的贡献。
  • 若 xj>0x_j>0，则我们考虑有序 jj 元组 (x1,x2,…,xj−1)(x_1,x_2,\dots,x_j-1)，我们只需统计它的数量。贡献就是 gi−1,jg_{i-1,j}。
  • 两者相加就是总数。
那么我们考虑求解转化后的组合意义。这是一个经典的问题，我们可以考虑“插板法”，容易得出 gi,j=(i+j−1j−1)g_{i,j}=\binom{i+j-1}{j-1}。
关于这个问题的推导
我们将 ii 分成 ii 个 11 相加。那么 11 之间会产生 i−1i-1 个“间隔”，在“间隔”中我们可以放“板”。一个“板”会将其所在的极大 11 块分为 22 份，即生成了两段 xx 的和。
对于原问题，因为 xpx_p 可以取到 00 且要求有序，所以“板”可以插在第一个 11 的左侧或最后的 11 右侧（即开头结尾），这样就有了 i+1i+1 个“间隔”。
同时，我们关注到多个“板”可以同时放在一个“间隔”中，表示 xx 中存在一段 00，所以我们不妨考虑增加若干个“通配间隔”，用于容纳这些重复的“板”。因为“板”一共需要 j−1j-1 个（拆成 jj 段，即 jj 个元），所以我们需要 j−2j-2 个“通配间隔”，与原来的间隔合起来可得总共有 i+j−1i+j-1 个“间隔”，那么答案就显而易见了：共 (i+j−1j−1)\binom{i+j-1}{j-1} 个放“板”的方式，也就是这么多组 xx 的可行解。此时对于边界情况也是没问题的。
我们要求的是 gj+1,ig_{j+1,i}，带入得 (i+ji−1)\binom{i+j}{i-1}，这便是第一部分的贡献。
类似地，第二部分的贡献为 2(i+jj−1)2\binom{i+j}{j-1}。
接下来我们考虑第三部分。我们设 fn,m′f'_{n,m} 表示 fn,mf_{n,m} 所包含的 33 的贡献的总数。那么，我们容易得出递推式：
fi,j′={0i=0∨j=0fi−1,j′+fi,j−1′+1otherwise.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∨QP\lor Q 表示 PP 或 QQ，即 P,QP,Q 间至少有一个成立。
那么实际上 fi,jf_{i,j} 中 33 的贡献就是 3fi,j′3f'_{i,j}。
我们还是考虑赋予其组合意义。容易发现 fi,j′f'_{i,j} 实际上就是从平面上任意的 (x,y)(1≤x≤i,1≤y≤j)(x,y)(1\le x\le i,1\le y\le j) 仅向右、向下走到 (i,j)(i,j) 的不同路径数量。
关于这个组合意义的正确性
这个组合意义正确性的证明是显然的，因为走一步到 (i,j)(i,j) 只有两个方法：从 (i−1,j)(i-1,j) 或 (i,j−1)(i,j-1) 过来。所以将 fi−1,j′f'_{i-1,j} 和 fi,j−1′f'_{i,j-1} 相加。同时我们发现这么处理会漏掉 (i,j)(i,j) 走到 (i,j)(i,j) 本身的方案，所以加 11 即可。
然后我们考虑翻转整个平面，使 (i,j)(i,j) 变为 (1,1)(1,1)，那么对应地，我们就要求从任意的 (x,y)(1≤x≤i,1≤y≤j)(x,y)(1\le x\le i,1\le y\le j) 仅向上、向左走到 (1,1)(1,1) 的不同路径数量。容易得出为 ∑p=1i∑q=1j(p+q−2p−1)\sum\limits_{p=1}^i\sum\limits_{q=1}^j\binom{p+q-2}{p-1}。
关于路径计数
从 (x,y)(x,y) 仅向上、向左走到 (1,1)(1,1) 的方案计数我们可以考虑其每步的变化量。
容易发现其必向上 x−1x-1 步，向左 y−1y-1 步，不同的路径实际上是不同的变化量的组合。
那么此时其方案数就有 (x+y−2x−1)\binom{x+y-2}{x-1}。
我们把我们推出的求和式子带入递推式：
fi,j′=fi−1,j′+fi,j−1′+1⇓∑p=1i∑q=1j(p+q−2p−1)=∑p=1i−1∑q=1j(p+q−2p−1)+∑p=1i∑q=1j−1(p+q−2p−1)+1=2∑p=1i−1∑q=1j−1(p+q−2p−1)+∑p=1i−1(p+j−2j−1)+∑q=1j−1(q+i−2i−1)+1⇓(i+j−2i−1)=∑p=1i−1∑q=1j−1(p+q−2p−1)+1⇓fi−1,j−1′=(i+j−2i−1)−1⇓fi,j′=(i+ji)−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}
那么我们容易得到 33 对 fi,jf_{i,j} 的贡献就是 3(i+ji)−33\binom{i+j}i-3，求和可得：
fi,j=(i+ji−1)+2(i+jj−1)+3(i+jj)−3f_{i,j}=\binom{i+j}{i-1}+2\binom{i+j}{j-1}+3\binom{i+j}{j}-3
带入一开始的式子，则有：
1+(m−1n−1)+fm−n,n−1=1+(m−1n−1)+(m−1n)+2(m−1n−2)+3(m−1n−1)−3=4(m−1n−1)+2(m−1n−2)+(m−1n)−2\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：
CPP
//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;
}

后记

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

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...