結果

問題 No.515 典型LCP
コンテスト
ユーザー gigime
提出日時 2017-05-05 23:31:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,718 bytes
コンパイル時間 1,878 ms
コンパイル使用メモリ 173,640 KB
実行使用メモリ 59,528 KB
最終ジャッジ日時 2024-09-14 09:15:30
合計ジャッジ時間 7,171 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 2 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

const ll pow1 = 1003,pow2 = 1007,mod1 = 1e9 + 7,mod2 = 1e9 + 9;
struct RollingHash{
	int n;
	vector<ll> dat,powTable;
	ll pow,mod;
	void init(string& str,ll pow,ll mod){
		n = str.size();
		this->pow = pow;
		this->mod = mod;
		dat.assign(n + 1,0);
		powTable.assign(n + 1,1);
		for(int i = 1;i <= n;i++){
			dat [i] = (dat [i - 1] * pow + str [i - 1]) % mod;
			powTable [i] = (powTable [i - 1] * pow) % mod;
		}
	}
	ll get(int l,int r){
		ll res = dat [r] - dat [l] * powTable [r - l];
		res = (res % mod + mod) % mod;
		return res;
	}
};
int N;
vector<string> S;
RollingHash rh [100000] [2];
char buffer [1000000];
ll M,X,D;

void get_query(int& a,int& b)
{
	a = (X / (N - 1)) + 1;
	b = (X % (N - 1)) + 1;
	if(a > b){
		swap(a,b);
	}
	else{
		b++;
	}
	X = (X + D) % (N * (N - 1));
}

int main()
{
	scanf("%d",&N);
	S.assign(N,"");
	FOR(i,0,N){
		scanf("%s",buffer);
		S [i] = buffer;
		rh [i] [0].init(S [i],pow1,mod1);
		rh [i] [1].init(S [i],pow2,mod2);
	}
	scanf("%lld%lld%lld",&M,&X,&D);
	
	ll ans = 0;
	FOR(i,0,M){
		int a,b;
		get_query(a,b);
		a--; b--;
		int ok = 0,ng = min(S [a].size(),S [b].size()) + 1,mid;
		while(ng - ok > 1){
			mid = (ok + ng) / 2;
			if(rh [a] [0].get(0,mid) == rh [b] [0].get(0,mid) && rh [a] [1].get(0,mid) == rh [b] [1].get(0,mid)){
				ok = mid;
			}
			else{
				ng = mid;
			}
		}
		ans += ok;
	}
	printf("%lld\n",ans);

	return 0;
}
0