結果
問題 | No.3082 Make Palindromic Multiple(Judge) |
ユーザー |
|
提出日時 | 2025-03-27 19:26:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,246 ms / 3,500 ms |
コード長 | 2,637 bytes |
コンパイル時間 | 4,259 ms |
コンパイル使用メモリ | 255,736 KB |
実行使用メモリ | 10,968 KB |
最終ジャッジ日時 | 2025-04-16 13:11:46 |
合計ジャッジ時間 | 14,420 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 73 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using u64 = uint64_t; template<typename T> std::vector<T> divisor(T n) { std::vector<T> res1; std::vector<T> res2; for (T i = 1; i * i <= n; i++) { if (n % i == 0) { res1.push_back(i); if (i != n / i) { res2.push_back(n / i); } } } for (u64 i = res2.size(); i >0; --i){ res1.push_back(res2[i - 1]); } return res1; } //* u64 mul(u64 a, u64 b) { // a*b mod 2^61-1 constexpr u64 p = (1ull << 61) - 1; const u64 m30 = (1ull << 30) - 1; const u64 m31 = (1ull << 31) - 1; u64 au = a >> 31; u64 ad = a & m31; u64 bu = b >> 31; u64 bd = b & m31; u64 mid = ad * bu + au * bd; u64 midu = mid >> 30; u64 midd = mid & m30; u64 res = ((au * bu * 2) % p + midu + (midd << 31) % p + (ad * bd) % p) % p; return res; } /*/ //* constexpr u64 p = 998244353; u64 mul(u64 a, u64 b) { return ((a % p) * (b % p)) % p; } //*/ u64 powmod(u64 base, u64 exp) { // base^exp mod MOD if (exp == 0) { return 1; } else if (exp % 2 == 0) { u64 t = powmod(base, exp / 2); return mul(t, t); } else { return mul(base, powmod(base, exp - 1)); } } u64 P=(1ull << 61) - 1; u64 r=37; u64 gethash(vector<string> &s,vector<u64> &t){ int n=s.size(); u64 ret=0; for(int i=0;i<n;i++){ u64 tmp=powmod(r,s[i].size()); u64 tmp2=powmod(tmp,t[i]); ret=mul(ret,tmp2); u64 plus=0; for(int j=0;j<s[i].size();j++){ plus=mul(plus,r); plus=(plus+(s[i][j]-'0'))%P; } tmp2=(tmp2-1+P)%P; tmp=(tmp-1+P)%P; u64 coef=mul(tmp2,powmod(tmp,P-2)); ret=(ret+mul(plus,coef))%P; } return ret; } using mint=modint998244353; mint R=3; u64 gethash998(vector<string> &s,vector<u64> &t){ int n=s.size(); mint ret=0; for(int i=0;i<n;i++){ mint tmp=R.pow(s[i].size()); mint tmp2=tmp.pow(t[i]); ret=ret*tmp2; mint plus=0; for(int j=0;j<s[i].size();j++){ plus=plus*R; plus=plus+mint(s[i][j]-'0'); } ret=ret+plus*(tmp2-1)/(tmp-1); } return ret.val(); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll k; cin>>k; vector<string> s(k); vector<u64> t(k); for(int i=0;i<k;i++) cin>>s[i]>>t[i]; u64 hash1=gethash(s,t),SORRY1=gethash998(s,t); reverse(s.begin(),s.end()); reverse(t.begin(),t.end()); for(int i=0;i<k;i++) reverse(s[i].begin(),s[i].end()); u64 hash2=gethash(s,t),SORRY2=gethash998(s,t); if(hash1==hash2&&SORRY1==SORRY2) puts("Yes"); else puts("No"); }