题解

思路

记 $c_b(Z)$ 为二进制串 $Z$ 中字符 $b$ 的出现次数。

做法

若 $c_1(X)=c_1(Y)$，两边长度相等当且仅当 $c_0(X)=c_0(Y)$；此时令 $T=S$ 即可，所以答案分别为 Yes 或 No。否则由长度相等可唯一确定 $|T|=|S|\bigl(c_0(Y)-c_0(X)\bigr)/\bigl(c_1(X)-c_1(Y)\bigr)$；若结果不是非负整数，则无解。

设算出的长度为 $m$。当 $X\ne Y$ 时，两个拼接式相等当且仅当 $S,T$ 都是同一个长度为 $\gcd(|S|,m)$ 的字符串的若干次重复，因此只需检查 $S_i=S_{i\bmod g}$ 是否对所有位置成立，其中 $g=\gcd(|S|,m)$；满足时总能选取相应的重复串作为 $T$。

复杂度

每组数据只需统计字符数并扫描一次 $S$，总时间复杂度为 $O\left(\sum(|S|+|X|+|Y|)\right)$，额外空间为 $O(1)$。