結果
問題 |
No.3082 Make Palindromic Multiple(Judge)
|
ユーザー |
![]() |
提出日時 | 2025-03-28 22:45:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,578 bytes |
コンパイル時間 | 2,377 ms |
コンパイル使用メモリ | 209,968 KB |
実行使用メモリ | 34,464 KB |
最終ジャッジ日時 | 2025-03-29 00:24:50 |
合計ジャッジ時間 | 8,477 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 70 WA * 1 |
ソースコード
//#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; using pli = pair<ll,int>; #define TEST cerr << "TEST" << endl #define AMARI 998244353 //#define AMARI 1000000007 #define el '\n' #define El '\n' #define YESNO(x) ((x) ? "Yes" : "No") #define YES YESNO(true) #define NO YESNO(false) #define REV_PRIORITY_QUEUE(tp) priority_queue<tp,vector<tp>,greater<tp>> #define NO_ANS(x) {cout << (x) << '\n'; return;} template <typename T> void inline VEC_UNIQ(vector<T> &v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return; } const long long B1 = 100LL; const long long B2 = 100000LL; const long long md = 1002120277LL; // ロリハ // hash(S) = s[0] * B**(m-1) + s[1] * B**(m-2) + ... + s[m-1] * B**0 //色んな型に対応するようにしているが、0を入れると壊れる(一致してない列を一致していると言い張ることがある)ので注意 template <typename T> class ococo_rollinghash { private: long long pb1 = 1, pb2 = 1; int n = 0; deque<T> deq; // めんどいので雑に適当な素数にしてるが、後で(1LL << 61) - 1にして適切な高速化もやりたい const long long md = 1002120277; //const long long md = 1000000007; string s; ll hash1 = 0LL,hash2 = 0LL; ll beki(ll a,ll b){ ll ans = 1,temp = a; while(b){ if(b % 2){ ans *= temp; ans %= md; } temp *= temp; temp %= md; b /= 2; } return ans; } ll g1 = beki(B1,md - 2),g2 = beki(B2,md - 2); public: void push_back(T c){ hash1 *= B1; hash1 += (ll)c; hash1 %= md; hash2 *= B2; hash2 += (ll)c; hash2 %= md; n++; deq.push_back((T)c % md); return; } void push_front(T c){ hash1 += beki(B1,n) * (ll)c; hash1 %= md; hash2 += beki(B2,n) * (ll)c; hash2 %= md; n++; deq.push_front((T)c % md); return; } void pop_back(void){ assert(n != 0); T c = deq.back(); deq.pop_back(); hash1 -= c; if(hash1 < 0)hash1 += md; hash1 *= g1; hash1 %= md; hash2 -= c; if(hash2 < 0)hash2 += md; hash2 *= g2; hash2 %= md; n--; return; } void pop_front(void){ assert(n != 0); T c = deq.front(); deq.pop_front(); ll temp; temp = beki(B1,n - 1) * (ll)c; temp %= md; hash1 -= temp; if(hash1 < 0)hash1 += md; temp = beki(B2,n - 1) * (ll)c; temp %= md; hash2 -= temp; if(hash2 < 0)hash2 += md; n--; return; } pll get_hash(void){ return pair(hash1,hash2); } bool empty(void){ return (n == 0); } }; ll beki(ll a,ll b){ b %= (md - 1); ll ans = 1,temp = a; while(b){ if(b % 2){ ans *= temp; ans %= md; } temp *= temp; temp %= md; b /= 2; } return ans; } inline ll mod_inv(ll a){ return beki(a,md - 2); } pll get_hash(vector<string> s,vector<ll> t){ int n = (int)s.size(); //for(int i = 0; i < n; i++)cerr << s[i] << ' ' << t[i] << el; ll h1 = 0LL,h2 = 0LL; for(int i = 0; i < n; i++){ ococo_rollinghash<char> rh; ll m = (int)s[i].size(); for(int j = 0; j < (int)m; j++){ rh.push_back(s[i][j]); } ll th1,th2; tie(th1,th2) = rh.get_hash(); //cerr << th1 << ' ' << th2 << el; th1 *= (beki(B1,m * (t[i] % (md - 1))) - 1LL); th1 %= md; th1 *= mod_inv(beki(B1,m) - 1); th1 %= md; th2 *= (beki(B2,m * (t[i] % (md - 1))) - 1LL); th2 %= md; th2 *= mod_inv(beki(B2,m) - 1); th2 %= md; //cerr << m * (t[i] % (md - 1)) << el; h1 *= beki(B1,(m * (t[i] % (md - 1)))); h1 += th1; h1 %= md; h2 *= beki(B2,(m * (t[i] % (md - 1)))); h2 += th2; h2 %= md; //cerr << h1 << ' ' << h2 << el; } return pair(h1,h2); } #define MULTI_TEST_CASE false void solve(void){ //問題を見たらまず「この問題設定から言えること」をいっぱい言う //一個回答に繋がりそうな解法が見えても、実装や細かい詰めに時間がかかりそうなら別の方針を考えてみる //ある程度考察しても全然取っ掛かりが見えないときは実験をしてみる //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く //複数の解法のアイデアを思いついた時は全部メモしておく //g++ -D_GLIBCXX_DEBUG -Wall -Wextra -O2 i.cpp -o o int k; cin >> k; vector<string> s(k),revs(k); vector<ll> t(k),revt(k); for(int i = 0; i < k; i++){ cin >> s[i] >> t[i]; revs[i] = s[i]; revt[i] = t[i]; reverse(revs[i].begin(),revs[i].end()); } reverse(revs.begin(),revs.end()); reverse(revt.begin(),revt.end()); /* for(int i = 0; i < k; i++){ cerr << s[i] << ' ' << t[i] << el; } for(int i = 0; i < k; i++){ cerr << revs[i] << ' ' << revt[i] << el; } */ cout << YESNO(get_hash(s,t) == get_hash(revs,revt)) << el; return; } void calc(void){ return; } signed main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE)cin >> t; while(t--){ solve(); } return 0; }