結果

問題 No.3082 Make Palindromic Multiple(Judge)
ユーザー 小高悠太郎
提出日時 2025-08-24 14:37:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,500 bytes
コンパイル時間 3,487 ms
コンパイル使用メモリ 288,072 KB
実行使用メモリ 14,504 KB
最終ジャッジ日時 2025-08-24 14:37:23
合計ジャッジ時間 10,233 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 71 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); ++i)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define fore(i, a) for(auto &i:a)
using ll = long long;
//https://yukicoder.me/problems/no/3082

//b:999999797, 999999883, 1000000007, 1000000009, 2147483647, 2147771771
struct roling_hash{
	vector<ll> H, B;
	ll n, b, mod;
	string s;
	roling_hash(string s_,ll b_, ll mod_){
		s = s_;b = b_; mod = mod_;
		n = s.size()+1;
		H.assign(n,0);
		B.assign(n,0);
		H[0] = 0;
		B[0] = 1;
		repi(i, 1, n){
			H[i] = (b*H[i-1]%mod+s[i-1])%mod;
			B[i] = B[i-1]*b%mod;
		}
	}

	ll get_hash(ll l,ll r){
		return (H[r+1] - B[r-l+1]*H[l]%mod+mod)%mod;
	}

	ll get_hash(string t){
		ll res=0;
		ll sz = t.size();
		rep(i, sz){
			res += B[sz-1-i]*t[i]%mod;
			res %= mod;
		}
		return res;
	}
};
long long random_large_ll(ll m, ll M) {
	static std::random_device rd;
	static std::mt19937_64 gen(rd());

	std::uniform_int_distribution<long long> dist(m, M);
	return dist(gen);
}
ll inverse(ll mod, ll val){
	ll x[2] = {mod, val};
	ll a[2] = {1, 0};
	ll i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i] -= x[i] / x[!i] * a[i];
		x[i] = x[i] % x[!i];
	}
	if(!i) a[!i] += mod;
	return a[!i];
}
void solve(){
	ll k; cin >> k;
	ll h1=0,h2=0;
  ll b = random_large_ll(2, 100100100);
	ll mod = 1000000009;
	string _(200001, '*');
	roling_hash HS(_,b,mod);
	ll bx=1;
	vector<string> s(k);
	vector<ll> t(k);
	rep(i, k)cin >> s[i] >> t[i];
	vector<ll> db1(61);
	db1[0] = b;
	rep(i, 60){
		db1[i+1] = db1[i]*db1[i];
		db1[i+1] %= mod;
	}
	rep(i, k){
		ll sz = s[i].size();
		string rev = s[i];
		reverse(all(rev));
		ll bs = 1;
		rep(j, 61){
			if((sz >> j) & 1){
				bs*=db1[j];
				bs%=mod;
			}
		}
		ll temp1 = HS.get_hash(s[i]);
		ll temp2 = HS.get_hash(rev);
		vector<ll> db2(61);
		db2[0] = bs;
		rep(j, 60){
			db2[j+1] = db2[j]*db2[j];
			db2[j+1] %= mod;
		}
		ll bst = 1;
		rep(j, 61){
			if((t[i] >> j) & 1){
				bst*=db2[j];
				bst%=mod;
			}
		}
		ll p = (1-bs+mod)%mod == 0 ? t[i]%mod:(((1-bst+mod)%mod)*inverse(mod, (1-bs+mod)%mod))%mod;
		ll p1 = p*temp1%mod;
		ll p2 = p*temp2%mod;
		h1 *= bst;
		h1 %= mod;
		h1 += p1;
		h1 %= mod;

		p2 *= bx;
		p2 %= mod;
		h2 += p2;
		h2 %= mod;

		bx *= bst;
		bx %= mod;
	}
	if(h1 == h2)cout << "Yes" << endl;
	else cout << "No" << endl;
}
			
int main() {
  solve();
}
0