結果

問題 No.3082 Make Palindromic Multiple(Judge)
ユーザー nouka28
提出日時 2025-03-28 23:23:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,001 bytes
コンパイル時間 7,787 ms
コンパイル使用メモリ 368,520 KB
実行使用メモリ 18,912 KB
最終ジャッジ日時 2025-03-29 00:25:22
合計ジャッジ時間 25,349 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 70 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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 P1=2147483647;
const lint P2=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)->vector<lint> {
        lint ret1=0;
        lint ret2=0;
        rep(i,K){
            // cout<<i<<" : "<<s[i]<<" "<<t[i]<<endl;
            lint q1=0,q2=0;
            for(auto&&e:s[i]){
                q1=(q1*R+(e-'0'))%P1;
                q2=(q2*R+(e-'0'))%P2;
            }
            lint sz=s[i].size();
            lint tmp1=modpow(R,sz,P1);
            lint tmp2=modpow(R,sz,P2);
            lint tmp3=geometric_progression(tmp1,t[i],P1);
            
            lint tmp4=geometric_progression(tmp2,t[i],P2);
            ret1=(ret1*modpow(R,sz*t[i],P1))%P1;
            
            ret2=(ret2*modpow(R,sz*t[i],P2))%P2;
            // cout<<"q : "<<q<<endl;
            // cout<<"tmp : "<<tmp<<endl;
            // cout<<"tmp2 : "<<tmp2<<endl;
            ret1=(ret1+q1*tmp3)%P1;
            ret2=(ret2+q2*tmp4)%P2;
        }
        // cout<<"ret : "<<ret<<endl;
        return {ret1,ret2};
    };
    set<vector<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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0