結果

問題 No.2030 Googol Strings
ユーザー 沙耶花沙耶花
提出日時 2022-08-05 21:46:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 191 ms / 2,000 ms
コード長 2,838 bytes
コンパイル時間 4,246 ms
コンパイル使用メモリ 257,220 KB
最終ジャッジ日時 2025-01-30 17:56:26
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000
struct rolling_hash{
long long t_hash;
static const long long MOD = (1LL<<61)-1;
static const long long b = 123456;
long long sz;
rolling_hash(){
sz = 0;
t_hash = 0;
}
rolling_hash(char c){
sz = 1;
t_hash = b*c;
}
long long mul(__int128 x,__int128 y){
__int128 t = x*y;
t = (t>>61) + (t&MOD);
if(t>=MOD)t -= MOD;
return t;
}
long long get_pow(long long sz){
long long cur = b,ret = 1;
rep(i,40){
if((sz>>i)&1){
ret = mul(ret,cur);
sz -= (1LL<<i);
}
cur = mul(cur,cur);
if(sz==0)break;
}
return ret;
}
rolling_hash &operator+=(const rolling_hash &another){
(*this).t_hash = mul((*this).t_hash,get_pow(another.sz));
(*this).t_hash += another.t_hash;
if((*this).t_hash>=MOD)(*this).t_hash -= MOD;
(*this).sz += another.sz;
return (*this);
}
rolling_hash operator+(const rolling_hash &another)const{
return (rolling_hash(*this)+=another);
}
rolling_hash &operator-=(const rolling_hash &another){
(*this).t_hash += MOD - mul(another.t_hash,get_pow((*this).sz-another.sz));
if((*this).t_hash>=MOD)(*this).t_hash -= MOD;
(*this).sz -= another.sz;
return (*this);
}
rolling_hash operator-(const rolling_hash &another)const{
return (rolling_hash(*this)-=another);
}
bool operator<(const rolling_hash &another)const{
if((*this).t_hash!=another.t_hash)return (*this).t_hash<another.t_hash;
return (*this).sz<another.sz;
}
bool operator==(const rolling_hash &another)const{
return ((*this).t_hash==another.t_hash && (*this).sz==another.sz);
}
};
//vector<long long> rolling_hash::power;
int main() {
int _t;
cin>>_t;
rep(_,_t){
string x,y;
cin>>x>>y;
int n =x.size(),m = y.size();
vector<rolling_hash> Rx(n+1),Ry(m+1);
rep(i,n){
Rx[i+1] = rolling_hash(x[i]);
Rx[i+1] = Rx[i] + Rx[i+1];
}
rep(i,m){
Ry[i+1] = rolling_hash(y[i]);
Ry[i+1] = Ry[i] + Ry[i+1];
}
vector<rolling_hash> dpx(40),dpy(40);
dpx[0] = Rx.back();
dpy[0] = Ry.back();
for(int i=1;i<40;i++){
dpx[i] = dpx[i-1] + dpx[i-1];
dpy[i] = dpy[i-1] + dpy[i-1];
}
long long L = lcm(n,m)+1;
long long ok = 0,ng = L + 1;
while(ng-ok>1LL){
long long mid = (ok+ng)/2;
rolling_hash X,Y;
rep(i,40){
if(((mid/n)>>i)&1)X += dpx[i];
if(((mid/m)>>i)&1)Y += dpy[i];
}
X += Rx[mid%n];
Y += Ry[mid%m];
if(X==Y)ok = mid;
else ng = mid;
}
//cout<<ok<<endl;
if(ok==L){
if(n>m)cout<<'X'<<endl;
else cout<<'Y'<<endl;
}
else{
if(x[ok%n]>y[ok%m])cout<<"X"<<endl;
else cout<<"Y"<<endl;
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0