結果

問題 No.3082 Make Palindromic Multiple(Judge)
ユーザー kaichou243
提出日時 2025-03-27 19:18:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,526 bytes
コンパイル時間 1,987 ms
コンパイル使用メモリ 199,708 KB
実行使用メモリ 10,952 KB
最終ジャッジ日時 2025-03-28 01:24:10
合計ジャッジ時間 13,338 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 64 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using u64 = uint64_t;

template<typename T>
std::vector<T> divisor(T n) {
	std::vector<T> res1;
	std::vector<T> res2;

	for (T i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			res1.push_back(i);
			if (i != n / i) {
				res2.push_back(n / i);
			}

		}
	}
	for (u64 i = res2.size(); i  >0; --i){
		res1.push_back(res2[i - 1]);
	}
	return res1;
}
//*
u64 mul(u64 a, u64 b) { // a*b mod 2^61-1
	constexpr u64 p = (1ull << 61) - 1;
	const u64 m30 = (1ull << 30) - 1;
	const u64 m31 = (1ull << 31) - 1;
	u64 au = a >> 31;
	u64 ad = a & m31;
	u64 bu = b >> 31;
	u64 bd = b & m31;
	u64 mid = ad * bu + au * bd;
	u64 midu = mid >> 30;
	u64 midd = mid & m30;
	u64 res = ((au * bu * 2) % p + midu + (midd << 31) % p + (ad * bd) % p) % p;
	return res;
}
/*/
//*
constexpr u64 p = 998244353;

u64 mul(u64 a, u64 b) {
	return ((a % p) * (b % p)) % p;
}
//*/
u64 powmod(u64 base, u64 exp) { // base^exp mod MOD
	if (exp == 0) {
		return 1;
	} else if (exp % 2 == 0) {
		u64 t = powmod(base, exp / 2);
		return mul(t, t);
	} else {
		return mul(base, powmod(base, exp - 1));
	}
}
u64 P=(1ull << 61) - 1;
u64 r;
u64 gethash(vector<string> &s,vector<u64> &t){
    int n=s.size();
    u64 ret=0;
    for(int i=0;i<n;i++){
        u64 tmp=powmod(r,s[i].size());
        u64 tmp2=powmod(tmp,t[i]);
        ret=mul(ret,tmp2);
        u64 plus=0;
        for(int j=0;j<s[i].size();j++){
            plus=mul(plus,r);
            plus=(plus+(s[i][j]-'0'))%P;
        }
        tmp2=(tmp2-1+P)%P;
        tmp=(tmp-1+P)%P;
        u64 coef=mul(tmp2,powmod(tmp,P-2));
        ret=(ret+mul(plus,coef))%P;
    }
    return ret;
}
ll rand_int(ll l, ll r) { //[l, r]
    #ifdef LOCAL
    static mt19937_64 gen;
    #else
    static random_device rd;
    static mt19937_64 gen(rd());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll k; cin>>k;
    vector<string> s(k);
    vector<u64> t(k);
    for(int i=0;i<k;i++) cin>>s[i]>>t[i];
    while(true){
        r=rand_int(2,P-2);
        bool retry=false;
        for(int i=0;i<k;i++) if(powmod(r,s[i].size())==1||powmod(r,t[i])==1){
            retry=true;
            break;
        }
        if(!retry) break;
    }
    u64 hash1=gethash(s,t);
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    for(int i=0;i<k;i++) reverse(s[i].begin(),s[i].end());
    u64 hash2=gethash(s,t);
    if(hash1==hash2) puts("Yes");
    else puts("No");
}
0