当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

给定两个 01 串 X, Y,其中可以包含若干问号表示这一位可以是 0 也可以是 1。求有多少对这样的二元字符串 (S, T) 满足 |S|, |T| \leq n 且将 X, Y 的每个 0 1 替换为 S, T 后两个串相等。

|X|, |Y|, n \leq 3 \times 10^5

我们先考虑不存在问号的情况

定义字符串减法为加法的逆运算,即若存在 A + B = C 的则 C - B = A

定义两个字符串 S, T(不妨假设 |S| \leq |T|)是互质的,当且仅当他们存在共同的循环节,即 S=TS \perp (T-S)

定理1:字符串对 (S, T) 可以作为答案当且仅当 S \perp TX = Y

先将 X, Y 共同减去 \operatorname{LCP} (X, Y),得到一端开头为 0 另一端为 1(不妨假设 |S| \leq |T|),则 ST 的前缀,然后将两端同时减去 S 继续比较。若 X \neq Y 则可以得到 S \perp T

定理2:结果只与 X, Y 中的 0, 1 个数差有关。

对于 XY 中一堆相邻的 0, 1,因为 S \perp T,将他们交换后对答案不产生影响。

定义 \Delta_0 = \operatorname{cnt}_0(S) - \operatorname{cnt}_0(T), \Delta_1 = \operatorname{cnt}_1(S) - \operatorname{cnt}_1(T)

  1. \Delta_0 = \Delta_1 = 0,则相当于求 S \perp T 的二元字符串组对数。即 \sum_{i=1}^n \sum_{j=1}^n 2^{\gcd(i, j)}
  2. \Delta_0 \times \Delta_1 \geq 0\Delta_0 + \Delta_1 \neq 0,则显然不合法。
  3. \Delta_0 \times \Delta_1 < 0,不妨设 |S| \leq |T|。若 \Delta_0 + \Delta_1 = 0,则 S = T,否则有 \Delta_0 \times S = \Delta_1 \times T \Rightarrow \Delta_0 \times S = \Delta_1 (S + X) \Rightarrow (\Delta_0 - \Delta_1) S = \Delta_1 \times X 即可转化为一个子问题。答案即 2^{n/\max(\frac{\Delta_0} g, \frac{\Delta_1} g) + 1} - 2,其中 g = \gcd(\Delta_0, \Delta_1)

考虑带问号的情况,假设 X 中有 x 个问号,其中 i 个是 0Y 中有 y 个问号,其中 j 个是 0。则

\begin{aligned} \Delta_0 &= \Delta_0' + (i - j) \\ \Delta_1 &= \Delta_1' + (x - y) - (i - j) \\ \end{aligned}

显然 \Delta_0', \Delta_1', (a-b) 都是确定的,且 (c-d) \in [-3\times 10^5, 3\times 10^5],可以预处理出答案。

\begin{aligned} \mathit{Ans} &= \sum_{i=0}^x \sum_{j=0}^y \binom xi \binom yj f(i-j) \\ &= \sum_{d} f(d) \sum_{i=0}^x \binom xi \binom y{i-d} \\ &= \sum_{d} f(d) \binom {x+y} {y+d} \\ \end{aligned}

最后一步组合数的转化考虑组合意义即可得证。

巧妙的思路 字符串 辗转相除 Favorite

仅有一条评论

  1. orz memset0

macOS 外接显示器的一些体验
上一篇 «
配置 SSH config 使用跳板机连接
» 下一篇