結果

問題 No.515 典型LCP
ユーザー momoyuumomoyuu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0