結果

問題 No.3082 Make Palindromic Multiple(Judge)
ユーザー kaichou243
提出日時 2025-03-27 19:26:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,246 ms / 3,500 ms
コード長 2,637 bytes
コンパイル時間 4,259 ms
コンパイル使用メモリ 255,736 KB
実行使用メモリ 10,968 KB
最終ジャッジ日時 2025-04-16 13:11:46
合計ジャッジ時間 14,420 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 73
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace atcoder;
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=37;
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;
}
using mint=modint998244353;
mint R=3;
u64 gethash998(vector<string> &s,vector<u64> &t){
    int n=s.size();
    mint ret=0;
    for(int i=0;i<n;i++){
        mint tmp=R.pow(s[i].size());
        mint tmp2=tmp.pow(t[i]);
        ret=ret*tmp2;
        mint plus=0;
        for(int j=0;j<s[i].size();j++){
            plus=plus*R;
            plus=plus+mint(s[i][j]-'0');
        }
        ret=ret+plus*(tmp2-1)/(tmp-1);
    }
    return ret.val();
}
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];
    u64 hash1=gethash(s,t),SORRY1=gethash998(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),SORRY2=gethash998(s,t);
    if(hash1==hash2&&SORRY1==SORRY2) puts("Yes");
    else puts("No");
}
0