题解：AT_arc181_b [ARC181B] Annoying String Problem

Shxt_Plus · 2024-08-13 21:03:09 · 题解

个人认为思路比较自然的一道题。

题意：定义 f(S,T,X) 为一个字符串 Q：

对于 1,2,3,\cdots ,len_x，若 X_i 为 0，把 S 拼到字符串 Q 后面，若 X_i 为 1，把 T 拼到字符串 Q 后面。

给出 S,T,X，问你能否构造出一个 T 使得 f(S,T,X) =f(S,T,Y)。

显然可以通过解一个一元一次方程算出 T 的长度。

考虑 X 与 Y 第一个不相同的位置，发现 T 是 S 的不断循环，那么显然可以直接算出 T 的哈希值是多少，然后直接算出 f(S,T,X) 和 f(S,T,Y) 的哈希值再比较即可。

Code:

#include<bits/stdc++.h>
#define int long long
using ll=long long;
using namespace std;
const ll mod=998244353,base=131;
int t;
ll po(ll x,int n)
{
    ll tmp=1;
    while(n)
    {
        if(n&1)tmp=tmp*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return tmp;
}
signed main()
{
    cin>>t;
    while(t--)
    {
        string s,x,y;
        cin>>s>>x>>y;
        int m=s.size();
        ll ht=0,hs=0;
        int a0=0,b0=0,a1=0,b1=0;
        for(int i=0;i<x.size();i++)
        {
            if(x[i]=='0')a0++;
            else a1++;
        }
        for(int i=0;i<y.size();i++)
        {
            if(y[i]=='0')b0++;
            else b1++;
        }
        if(a0==b0)
        {
            cout<<"Yes\n";
            continue;
        }
        if(a1==b1)
        {
            cout<<"No\n";
            continue;
        }
        int u=m*(b0-a0);
        if(u%(a1-b1)!=0)
        {
            cout<<"No\n";
            continue;
        }
        u/=(a1-b1);
        if(u<0)
        {
            cout<<"No\n";
            continue;
        }
        for(int i=0;i<m;i++)
        {
            hs+=po(base,i)*(s[i]-'a'+1)%mod;
            hs%=mod;
        }
        for(int i=0;i<u/m;i++)
        {
            ht+=po(base,i*m)*hs%mod;
            ht%=mod;
        }
        for(int i=u/m*m;i<u;i++)
        {
            ht+=po(base,i)*(s[i%m]-'a'+1)%mod;
            ht%=mod;
        }
        ll hx=0,hy=0,lenx=0,leny=0;
        for(int i=0;i<x.size();i++)
        {
            if(x[i]=='0')hx+=po(base,lenx)*hs%mod,lenx+=m,lenx%=(mod-1);
            else hx+=po(base,lenx)*ht%mod,lenx+=u,lenx%=mod-1;
            hx%=mod;
        }
        for(int i=0;i<y.size();i++)
        {
            if(y[i]=='0')hy+=po(base,leny)*hs%mod,leny+=m,leny%=(mod-1);
            else hy+=po(base,leny)*ht%mod,leny+=u,leny%=(mod-1);
            hy%=mod;
        }
        if(hx==hy)
        {
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }
    return 0;
}