萌萌哒：题解

思路推导

每个数位可以看作一个变量。区间相等限制只会产生“两个位置必须取相同数字”的等价关系。设所有位置最终被划分成 $c$ 个等价类。包含位置 $1$ 的等价类不能取 $0$，有 $9$ 种选择；其余每个等价类有 $10$ 种选择，所以答案为

[ 9\times 10^{c-1}\bmod (10^9+7). ]

问题转化为高效求出位置等价关系的传递闭包。

做法

对每个满足 $2^k\le n$ 的 $k$，为所有长度为 $2^k$ 的连续块建立一层并查集。层 $k$ 中起点为 $i$ 的节点表示子串 $S_i\cdots S_{i+2^k-1}$。

处理一条长度为 $L$ 的区间相等限制时，令 $k=\lfloor\log_2 L\rfloor$。分别合并两段的长度 $2^k$ 前缀块，再合并两段的长度 $2^k$ 后缀块。

处理完所有限制后，从最高层向最低层传播。若两个长度为 $2^k$ 的块相等，那么它们的左半块分别相等，右半块也分别相等。对高层每个节点，找到它所在集合的代表块，并在下一层合并对应的左右半块。

传播到 $k=0$ 后，最低层并查集的连通分量数就是 $c$。

正确性证明

取 $k=\lfloor\log_2 L\rfloor$，有 $2^k\le L<2^{k+1}$，因此两个长度为 $2^k$ 的前后缀覆盖整个长度为 $L$ 的区间。两段相等显然能推出两对块分别相等；反过来，两对块相等也保证了区间内每个偏移对应的数位相等，所以双块表示与原限制等价。

长度为 $2^k$ 的两个块相等，当且仅当其左右两个长度为 $2^{k-1}$ 的半块分别相等。自顶向下传播既不会增加原限制没有蕴含的关系，也不会遗漏高层块相等所蕴含的关系。

因此最低层连通关系恰好是全部原限制生成的数位等价关系的传递闭包。按等价类独立赋值，并单独排除最高位为零的情况，得到的计数公式正确。

复杂度分析

分层节点总数为 $O(n\log n)$。每条限制只进行常数次高层合并，下降传播扫描全部分层节点，因此时间复杂度为 $O((n+m)\log n\,\alpha(n\log n))$，空间复杂度为 $O(n\log n)$。

部分分说明

若所有限制长度均为 $1$，直接在 $n$ 个位置上使用普通并查集，时间复杂度为 $O((n+m)\alpha(n))$。

若 $n,m\le 3000$，可以把每条区间限制逐位置展开。设全部区间长度之和为 $T$，时间复杂度为 $O(T\alpha(n))$，空间复杂度为 $O(n)$。