結果

問題 No.3082 Make Palindromic Multiple(Judge)
コンテスト
ユーザー applejam
提出日時 2025-04-05 01:07:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,172 bytes
コンパイル時間 3,655 ms
コンパイル使用メモリ 183,596 KB
実行使用メモリ 11,068 KB
最終ジャッジ日時 2025-04-05 01:07:26
合計ジャッジ時間 12,705 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 47 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
class RollingHash{
    private:
        ll base1;
        ll base2;
        vector<mint> rh1;
        vector<mint> rh2;
        vector<mint> pow1;
        vector<mint> pow2;
    
    public:
        RollingHash(const string &s, ll b1, ll b2){
            base1 = b1;
            base2 = b2;
            int len = s.size();
            rep(i, len){
                if(i==0){
                    pow1.push_back(1);
                    pow2.push_back(1);
                    rh1.push_back(mint(s[i] - '0'));
                    rh2.push_back(mint(s[i] - '0'));
                    continue;
                }
                pow1.push_back(pow1[i-1]*mint(b1));
                pow2.push_back(pow2[i-1]*mint(b2));
                rh1.push_back(mint(s[i] - '0') + rh1[i-1]*mint(b1));
                rh2.push_back(mint(s[i] - '0') + rh2[i-1]*mint(b2));
            }
        }

        pair<mint, mint> getHash(int l, int r){// 0-indexed
            mint a = rh1[r];
            mint b = rh2[r];
            if(l > 0){
                a -= rh1[l-1]*pow1[r-l+1];
                b -= rh2[l-1]*pow2[r-l+1];
            }
            return {a, b};
        }
};

mint sum(ll n, mint b){
    return (mint(b).pow(n) - 1)/(b-1);
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int k; cin >> k;
    vector<pair<string, ll>> vp(k);
    mint len = 0;
    rep(i, k){
        string s; ll t; cin >> s >> t;
        vp[i] = {s, t};
        len += mint(s.length()) * mint(t);
    }
    ll b1 = 99824443, b2 = 100000007;
    mint b3 = 0, b4 = 0;
    mint nlen = len;
    rep(i, k){
        auto [s, t] = vp[i];
        nlen -= mint(s.length()) *mint(t);
        int l = s.length();
        RollingHash rh = RollingHash(s, b1, b2);
        auto [c, d] = rh.getHash(0, s.length()-1);
        b3 += (c * sum(t, mint(b1).pow(l)))*mint(b1).pow(nlen.val());
        b4 += (d * sum(t, mint(b2).pow(l)))*mint(b2).pow(nlen.val());
    }
    mint b5 = 0, b6 = 0;
    mint rlen = len;
    drep(i, k){
        auto [s, t] = vp[i];
        rlen -= mint(s.length()) * mint(t);
        string u = s;
        int l = u.length();
        reverse(all(u));
        RollingHash rh = RollingHash(u, b1, b2);
        auto [c, d] = rh.getHash(0, u.length()-1);
        b5 += (c * sum(t, mint(b1).pow(l)))*mint(b1).pow(rlen.val());
        b6 += (d * sum(t, mint(b2).pow(l)))*mint(b2).pow(rlen.val());
    }
    if(b3.val() == b5.val() && b4.val() == b6.val()){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
0