結果

問題 No.3082 Make Palindromic Multiple(Judge)
コンテスト
ユーザー nouka28
提出日時 2025-03-28 23:18:58
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,714 bytes
コンパイル時間 7,283 ms
コンパイル使用メモリ 363,920 KB
実行使用メモリ 18,996 KB
最終ジャッジ日時 2025-03-28 23:19:17
合計ジャッジ時間 18,884 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 57 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using lint=__int128_t;

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define ALL(x) (x).begin(),(x).end()

#define int long long
#define fi first
#define se second

struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;

const lint P=998244353;
const lint R=100;

inline lint modpow(lint a,lint b,lint m){
	lint x=1;
	while(b){
		if(b&1)x=(x*a)%m;
		a=(a*a)%m;
		b>>=1;
	}
	return x;
}

inline lint geometric_progression(lint a,lint n,lint m){
	if(n==0)return 0;
	if(n%2==1){
		return (geometric_progression(a,n-1,m)*a+1)%m;
	}else{
		return (geometric_progression(a*a%m,n/2,m)*(1+a))%m;
	}
};


signed main(){
	int K;cin>>K;
	vector<string> S(K);
	vector<int> T(K);
	rep(i,K)cin>>S[i]>>T[i];

	auto get_hash=[&](vector<string> s,vector<int> t){
		lint ret=0;

		rep(i,K){
			// cout<<i<<" : "<<s[i]<<" "<<t[i]<<endl;
			lint q=0;
			for(auto&&e:s[i])q=(q*R+(e-'0'))%P;
			lint sz=s[i].size();
			lint tmp=modpow(R,sz,P);
			lint tmp2=geometric_progression(tmp,t[i],P);
			ret=(ret*modpow(R,sz*t[i],P))%P;
			// cout<<"q : "<<q<<endl;
			// cout<<"tmp : "<<tmp<<endl;
			// cout<<"tmp2 : "<<tmp2<<endl;
			ret=(ret+q*tmp2)%P;
		}

		// cout<<"ret : "<<ret<<endl;

		return ret;
	};

	set<lint> st;

	rep(i,2){
		st.insert(get_hash(S,T));
		reverse(ALL(S));reverse(ALL(T));
		for(auto&&e:S)reverse(ALL(e));
	}

	if(st.size()==1)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
0