結果

問題 No.515 典型LCP
ユーザー momoyuumomoyuu
提出日時 2024-09-30 01:25:53
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
}
0