結果
問題 |
No.3082 Make Palindromic Multiple(Judge)
|
ユーザー |
![]() |
提出日時 | 2025-03-28 22:59:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,162 ms / 3,500 ms |
コード長 | 1,827 bytes |
コンパイル時間 | 3,308 ms |
コンパイル使用メモリ | 289,452 KB |
実行使用メモリ | 11,740 KB |
最終ジャッジ日時 | 2025-04-16 13:12:37 |
合計ジャッジ時間 | 14,458 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 73 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/modint> #define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++) #define ll long long int K; vector<string> S; vector<ll> T; bool isok(int MOD) { using mint = atcoder::modint; mint::set_mod(MOD); auto calc = [&]() -> mint { mint hash = 0; vector<mint> A(K); rep(i, 0, K) { A[i] = 0; mint t = 1; for (int j = (int)S[i].size()-1; j >= 0; j--) { A[i] += t * (S[i][j]-'0'); t *= 10; } } // rep(i, 0, K) cout << A[i].val() << " "; // cout << endl; ll sum = 0; for (int i = K-1; i >= 0; i--) { mint F = mint(10).pow(sum); mint G = mint(10).pow((int)S[i].size()); //1 + G + ... + G^T[i]-1 //G^T[i]-1/G-1 // cout << F.val() << " " << G.val() << " "; mint P = G.pow(T[i])-1; P /= (G-1); // cout << P.val() << " "; P *= F; P *= A[i]; // cout << P.val() << endl; hash += P; sum += T[i]%(MOD-1)*(int)S[i].size(); sum %= (MOD-1); } // cout << "hash : " << hash.val() << endl; return hash; }; mint h1 = calc(); reverse(S.begin(), S.end()); reverse(T.begin(), T.end()); for (string& s : S) reverse(s.begin(), s.end()); mint h2 = calc(); return h1 == h2; } int main() { cin >> K; S.resize(K); T.resize(K); rep(i, 0, K) cin >> S[i] >> T[i]; vector<int> MODS = {998244353, 1000000007, 1000000009, 1000000021, 1000000033}; bool f = true; for (int m : MODS) { bool t = isok(m); if (!t) f = false; } cout << (f? "Yes" : "No") << endl; }