# ARC181 - B Annoying String Problem

diff: 1633

https://atcoder.jp/contests/arc181/tasks/arc181_b

## 解法

明らかに$|f(S, T, X)| = |f(S, T, Y)|$が必要である。この等式を考えると$T$の長さを特定することができる。
- $|T|$の長さが非負整数でないならば即座にNoと分かる
- $\text{cnt}_{1}(X) = \text{cnt}_{1}(Y)$のときはコーナーケースだけど、このときの判定問題は自明

<br />

$|T|$は最大 $(5\times 10^{5})^{2}$程度になり得ることに注意。めっちゃでかい。
- $X = 0000000...., Y = 1$のときとか

<br />

一般性を失わず$X_{１} = 0, Y_{１} = 1$を仮定する。

1. $|S| \ge |T|$のとき、$T$は$S$の長さ$|T|$の接頭辞になる
1. $|S| \lt |T|$のとき、$T$の始め$|S|$文字は$S$と一致しなければならない。$|S| + 1$文字目以降に関しては$X_{2}, X_{3}, \dots$によって定まる。
2. $X_{2} = 1$ならば、$i\equiv j\pmod{|S|}\rightarrow T_{i} = T_{j}$が必要となり、$T$は$S$の繰り返し文字列になることがわかる
3. $X_{2} = 0$ならば、$T_{|S| + 1}, \dots T_{2|S|}$も$S$と一致する必要がある。$X_{3}$に関して同じ議論を進めることになる

結局の所$T$は$T_{i} = S_{i\mod{|S|}}$が成り立つ必要がある。すなわち$T$は$S$の繰り返し文字列になる。

$T$ が一意に定まった。しかも $S$のローリングハッシュが計算済と仮定すると $T$のローリングハッシュも$O(|X| + |Y|)$で計算することが可能である。

以上より、$f(S, T, X)$と$f(S, T, Y)$のローリングハッシュが計算できた。

## 実装

#include <bits/stdc++.h>
#include "Src/Algebra/Monoid/RollingHashMonoid.hpp"

using namespace zawa;

using Monoid = RollingHashMonoid;
using E = Monoid::Element;
using V = E::Value;

V E::base{
    E::randomValue(26)
};

E f(E S, E T, const std::string& X) {
    E res{};
    for (auto c : X) {
        res = Monoid::operation(res, c == '0' ? S : T);
    }
    return res;
}

bool solve() {
    std::string S, X, Y;
    std::cin >> S >> X >> Y;
    int a{(int)std::count(X.begin(), X.end(), '0')};
    int b{(int)std::count(X.begin(), X.end(), '1')};
    int c{(int)std::count(Y.begin(), Y.end(), '0')};
    int d{(int)std::count(Y.begin(), Y.end(), '1')};
    if (b == d) return a == c;
    if ((long long)(S.size() * (a - c)) % (d - b)) return false;
    long long len{(long long)S.size() * (a - c) / (d - b)};
    if (len < 0) return false;
    E prodS{};
    for (auto c : S) prodS = Monoid::operation(prodS, E{c});
    E prodT{};
    while (len >= (int)S.size()) {
        prodT = Monoid::operation(prodT, prodS);
        len -= (int)S.size();
    }
    for (int i{} ; i < len ; i++) {
        prodT = Monoid::operation(prodT, E{S[i]});
    }
    return f(prodS, prodT, X) == f(prodS, prodT, Y);
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int T;
    std::cin >> T;
    while (T--) {
        std::cout << (solve() ? "Yes" : "No") << '\n';
    }
}

提出リンク: https://atcoder.jp/contests/arc181/submissions/57933350

## 感想

コンテスト本番中に解けなかった問題。

ハッシュを使わない方針もあると思ったが、面倒で貼ってしまった。