結果
問題 | No.515 典型LCP |
ユーザー |
![]() |
提出日時 | 2024-09-30 01:25:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,369 bytes |
コンパイル時間 | 1,942 ms |
コンパイル使用メモリ | 155,640 KB |
実行使用メモリ | 103,488 KB |
最終ジャッジ日時 | 2024-09-30 01:26:00 |
合計ジャッジ時間 | 6,782 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | TLE * 1 -- * 14 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll = long long;#line 1 "hash/hashint.hpp"using namespace std;#include<vector>#include<chrono>#include<random>struct hashint{using ull = unsigned long long;ull x;const static ull mod = (1ll<<61) - 1;hashint():x(0){}hashint(ull _x):x(_x){}hashint& operator+=(const hashint a) {x += a.x;if(x>=mod) x -= mod;return (*this);}hashint& operator-=(const hashint a) {x += mod - a.x;if(x>=mod) x -= mod;return (*this);}hashint& operator*=(const hashint a) {x = mul(x,a.x);return (*this);}hashint operator+(const hashint a) const {hashint res(*this);return res += a;}hashint operator-(const hashint a) const {hashint res(*this);return res -= a;}hashint operator*(const hashint a) const {hashint res(*this);return res *= a;}ull val(){return x;}bool operator==(const hashint a) const {return x == a.x;}bool operator<(const hashint a) const {return x < a.x;}static ull mul(const ull a,const ull b) {\ull au = a >> 31;ull ad = a & ((1ull<<31)-1);ull bu = b >> 31;ull bd = b & ((1ull<<31)-1);ull res = au * bu * 2;ull mid = au * bd + ad * bu;ull midu = mid >> 30;ull midd = mid & ((1ull<<30)-1);res += midu + midd * (1ull<<31);res += ad * bd;res = (res>>61) + (res&((1ull<<61)-1));if(res>=mod) res -= mod;return res;}static ull modpow(ull x,ull k){ull res = 1;while(k){if(k&1) res = mul(res,x);x = mul(x,x);k >>= 1;}return x;}static bool isPrimitive(ull x) {for (auto &now:vector<ull>{2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321})if (modpow(x,(mod-1)/now)<=1) return false;return true;}static hashint get_base(){long long seed = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();mt19937_64 rnd(seed);uniform_int_distribution<ull> now(1,mod-1);ull base{};while (true){base = now(rnd);if(isPrimitive(base)) break;}return base;}};/*** @brief Hashint* @docs docs/hash/hashint.md*/#line 2 "hash/rollinghash.hpp"#include<cassert>template<typename H,typename T>struct rolling_hash{using ull = unsigned long long;struct hash{H x,b;hash():x(0),b(1){}hash(ull _x,ull _b):x(_x),b(_b){}hash(H _x,H _b):x(_x),b(_b){}ull val(){return x.val();}hash operator+=(const hash a){x = x * a.b + a.x;b *= a.b;return (*this);}hash operator+(const hash a){hash res(*this);return res += a;}bool operator==(const hash a){return x == a.x;}bool operator<(const hash a){return x < a.x;}};int n;static H base;vector<H> sum,powb;rolling_hash(T x){n = x.size();sum = vector<H>(n+1,0);powb = vector<H>(n+1,1);for(int i = 0;i<n;i++){sum[i+1] = sum[i] * base + x[i];powb[i+1] = powb[i] * base;}}hash get(int l,int r){assert(0<=l&&l<r&&r<=n);return hash(sum[r]-sum[l]*powb[r-l],powb[r-l]);}int lcp(int a,int b){int mx = min(n-a,n-b);int right = mx + 1;int left = 0;while(right-left>1){int mid = (right+left) / 2;if(get(a,a+mid).val()==get(b,b+mid).val()) left = mid;else right = mid;}return left;}};using rhash = rolling_hash<hashint,string>;using hint = rhash::hash;template<>hashint rhash::base = hashint::get_base();/*** @brief Rolling Hash* @docs docs/hash/rollinghash.md*/#include<map>int main(){cin.tie(nullptr);ios::sync_with_stdio(false);ll n;cin>>n;vector<string> s(n);for(int i = 0;i<n;i++) cin>>s[i];vector<rhash> rh;for(int i = 0;i<n;i++){rhash h(s[i]);rh.push_back(h);}map<pair<int,int>,int> memo;ll m,x,d;cin>>m>>x>>d;ll ans = 0;for(ll k = 1;k<=m;k++){ll i = (x/(n-1)) + 1;ll j = (x%(n-1)) + 1;if(i>j) swap(i,j);else j = j + 1;x = (x+d) % (n*(n-1));if(memo.find(make_pair(i,j))!=memo.end()){ans += memo[make_pair(i,j)];//cout<<memo[make_pair(i,j)]<<endl;continue;}ll left = 0;ll right;i--;j--;{if(s[i].size()<s[j].size()) right = s[i].size();else right = s[j].size();right++;}while(right-left>1){ll mid = (right+left) / 2;if(rh[i].get(0,mid)==rh[j].get(0,mid)) left = mid;else right = mid;}memo[make_pair(i,j)] = left;ans += left;}cout<<ans<<endl;}