結果

問題 No.515 典型LCP
ユーザー antaanta
提出日時 2017-05-06 01:30:28
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 234 ms / 1,000 ms
コード長 7,526 bytes
コンパイル時間 2,380 ms
コンパイル使用メモリ 184,240 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-09-14 10:04:39
合計ジャッジ時間 5,061 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 234 ms
10,496 KB
testcase_01 AC 229 ms
10,368 KB
testcase_02 AC 132 ms
5,888 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 94 ms
5,760 KB
testcase_06 AC 96 ms
5,760 KB
testcase_07 AC 95 ms
5,760 KB
testcase_08 AC 125 ms
5,888 KB
testcase_09 AC 104 ms
6,016 KB
testcase_10 AC 99 ms
5,888 KB
testcase_11 AC 100 ms
5,888 KB
testcase_12 AC 100 ms
5,888 KB
testcase_13 AC 96 ms
5,760 KB
testcase_14 AC 9 ms
5,888 KB
testcase_15 AC 68 ms
5,888 KB
testcase_16 AC 68 ms
5,888 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }


template<typename Val, typename Compare = std::less<Val>, int BlockSize = 10>
class DirectRMQ {
public:
	typedef int Index;	//今のところ大きくともintを仮定している(queryとか)
	typedef char InBlockIndex;
	typedef InBlockIndex(*BlockTypeRef)[BlockSize];

	DirectRMQ(Compare comp_ = Compare()) :
		blockTypes(0), innerBlockTable(0), sparseTable(0) {
		comp = comp_;
		calcBallotNumbers();
		buildInnerBlockTable();
	}
	~DirectRMQ() {
		delete[] innerBlockTable;
		delete[] blockTypes; delete[] sparseTable;
	}

	void build(const Val *a, Index n) {
		blocks = (n + BlockSize - 1) / BlockSize;
		stHeight = 0; while (1 << stHeight < blocks) ++ stHeight;
		delete[] blockTypes; delete[] sparseTable;

		blockTypes = new BlockTypeRef[blocks];
		calcBlockTypes(a, n);
		buildInnerBlockTable(a, n);
		sparseTable = new Index[blocks * stHeight];
		buildSparseTable(a);
	}

	//[l,r]の閉区間
	Index query(const Val *a, Index l, Index r) const {
		Index x = l / BlockSize, y = r / BlockSize, z = y - x;
		if (z == 0) return x * BlockSize + blockTypes[x][l % BlockSize][r % BlockSize];
		if (z == 1) return assumeleft_minIndex(a,
			x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1],
			y * BlockSize + blockTypes[y][0][r % BlockSize]);
		z -= 2;
		Index k = 0, s;
		s = ((z & 0xffff0000) != 0) << 4; z >>= s; k |= s;
		s = ((z & 0x0000ff00) != 0) << 3; z >>= s; k |= s;
		s = ((z & 0x000000f0) != 0) << 2; z >>= s; k |= s;
		s = ((z & 0x0000000c) != 0) << 1; z >>= s; k |= s;
		s = ((z & 0x00000002) != 0) << 0; z >>= s; k |= s;
		return assumeleft_minIndex(a
			, assumeleft_minIndex(a,
				x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1],
				sparseTable[x + 1 + blocks * k])
			, assumeleft_minIndex(a,
				sparseTable[y + blocks * k - (1 << k)],
				y * BlockSize + blockTypes[y][0][r % BlockSize])
		);
	}

	Val queryVal(const Val *a, Index l, Index r) const {
		Index x = l / BlockSize, y = r / BlockSize, z = y - x;
		if (z == 0) return a[x * BlockSize + blockTypes[x][l % BlockSize][r % BlockSize]];
		Val edge = minVal(
			a[x * BlockSize + blockTypes[x][l % BlockSize][BlockSize - 1]],
			a[y * BlockSize + blockTypes[y][0][r % BlockSize]]);
		if (z == 1) return edge;
		z -= 2;
		Index k = 0, s;
		s = ((z & 0xffff0000) != 0) << 4; z >>= s; k |= s;
		s = ((z & 0x0000ff00) != 0) << 3; z >>= s; k |= s;
		s = ((z & 0x000000f0) != 0) << 2; z >>= s; k |= s;
		s = ((z & 0x0000000c) != 0) << 1; z >>= s; k |= s;
		s = ((z & 0x00000002) != 0) << 0; z >>= s; k |= s;
		return minVal(edge, minVal(
			a[sparseTable[x + 1 + blocks * k]],
			a[sparseTable[y + blocks * k - (1 << k)]]));
	}
private:
	Compare comp;

	int ballotNumbers[BlockSize + 1][BlockSize + 1];
	InBlockIndex(*innerBlockTable)[BlockSize][BlockSize];

	Index blocks;
	int stHeight;
	BlockTypeRef *blockTypes;
	Index *sparseTable;

	inline Index minIndex(const Val *a, Index x, Index y) const {
		return comp(a[x], a[y]) || (a[x] == a[y] && x < y) ? x : y;
	}
	inline Index assumeleft_minIndex(const Val *a, Index x, Index y) const {
		return comp(a[y], a[x]) ? y : x;
	}

	inline Val minVal(Val x, Val y) const {
		return comp(y, x) ? y : x;
	}

	void buildSparseTable(const Val *a) {
		Index *b = sparseTable;
		if (stHeight) for (Index i = 0; i < blocks; i ++)
			b[i] = i * BlockSize + blockTypes[i][0][BlockSize - 1];
		for (Index t = 1; t * 2 < blocks; t *= 2) {
			std::memcpy(b + blocks, b, blocks * sizeof(Index));
			b += blocks;
			for (Index i = 0; i < blocks - t; ++ i)
				b[i] = assumeleft_minIndex(a, b[i], b[i + t]);
		}
	}

	void buildInnerBlockTable(const Val *a, Index n) {
		for (Index i = 0; i < blocks; i ++) {
			BlockTypeRef table = blockTypes[i];
			if (table[0][0] != -1) continue;
			const Val *p = getBlock(a, n, i);
			for (InBlockIndex left = 0; left < BlockSize; left ++) {
				Val minV = p[left];
				InBlockIndex minI = left;
				for (InBlockIndex right = left; right < BlockSize; right ++) {
					if (comp(p[right], minV)) {
						minV = p[right];
						minI = right;
					}
					table[left][right] = minI;
				}
			}
		}
	}

	//端っこのブロック用に関数内staticなテンポラリ配列を返す
	const Val *getBlock(const Val *a, Index n, Index i) {
		Index offset = i * BlockSize;
		if (offset + BlockSize <= n)
			return a + offset;
		else {
			static Val tmp_a[BlockSize];
			std::copy(a + offset, a + n, tmp_a);
			Val maxVal = Val();
			for (Index j = i; j < n; j ++)	//iでなくoffsetでは？(動作には問題ないし計算量もほとんど変わらないけれど…)(バグるのが嫌なので(今まで動いていたので)直すのは後にする)
				if (comp(maxVal, a[j])) maxVal = a[j];
			std::fill(tmp_a + (n - offset), tmp_a + BlockSize, maxVal);
			return tmp_a;
		}
	}

	void calcBlockTypes(const Val *a, Index n) {
		Val tmp_rp[BlockSize + 1];
		for (Index i = 0; i < blocks; i ++)
			blockTypes[i] = calcBlockType(getBlock(a, n, i), tmp_rp);
	}

	BlockTypeRef calcBlockType(const Val *a, Val *rp) {
		int q = BlockSize, N = 0;
		for (int i = 0; i < BlockSize; i ++) {
			while (q + i - BlockSize > 0 && comp(a[i], rp[q + i - BlockSize])) {
				N += ballotNumbers[BlockSize - i - 1][q];
				q --;
			}
			rp[q + i + 1 - BlockSize] = a[i];
		}
		return innerBlockTable[N];
	}

	void calcBallotNumbers() {
		for (int p = 0; p <= BlockSize; p ++) {
			for (int q = 0; q <= BlockSize; q ++) {
				if (p == 0 && q == 0)
					ballotNumbers[p][q] = 1;
				else if (p <= q)
					ballotNumbers[p][q] =
					(q ? ballotNumbers[p][q - 1] : 0) +
					(p ? ballotNumbers[p - 1][q] : 0);
				else
					ballotNumbers[p][q] = 0;
			}
		}
	}

	void buildInnerBlockTable() {
		int numberOfTrees = ballotNumbers[BlockSize][BlockSize];
		innerBlockTable = new InBlockIndex[numberOfTrees][BlockSize][BlockSize];
		for (int i = 0; i < numberOfTrees; i ++)
			innerBlockTable[i][0][0] = -1;
	}
};

int main() {
	int N;
	while (~scanf("%d", &N)) {
		vector<pair<string, int>> strings(N);
		rep(i, N) {
			char buf[800001];
			scanf("%s", buf);
			strings[i] = { string(buf), i };
		}
		sort(strings.begin(), strings.end());
		vector<int> index(N, -1);
		rep(i, N)
			index[strings[i].second] = i;
		vector<int> lcp(N, 0);
		rep(i, N - 1) {
			const auto &A = strings[i].first, &B = strings[i + 1].first;
			int j = 0;
			for (; j != A.size() && j != B.size() && A[j] == B[j]; ++ j);
			lcp[i] = j;
		}
		DirectRMQ<int> rmq;
		rmq.build(lcp.data(), N);
		int M; long long X; long long D;
		scanf("%d%lld%lld", &M, &X, &D);
		ll mod = (ll)N * (N - 1);
		ll anssum = 0;
		rer(k, 1, M) {
			int i = (int)(X / (N - 1)) + 1;
			int j = (int)(X % (N - 1)) + 1;
			if (i > j) swap(i, j);
			else j = j + 1;

			{
				int x = index[i - 1], y = index[j - 1];
				if (x > y) swap(x, y);
				int ans = x == y ?
					(int)strings[i].first.size() :
					rmq.queryVal(lcp.data(), x, y - 1);
				anssum += ans;
			}

			X += D;
			if (X >= mod) X -= mod;
		}
		printf("%lld\n", anssum);
	}
	return 0;
}
0