結果
問題 | 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 |
ソースコード
#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 1000000000000struct 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;}