結果

問題 No.3014 多項式ハッシュに関する教育的な問題
ユーザー antaanta
提出日時 2015-10-21 16:31:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,163 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 23,888 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-29 17:19:00
合計ジャッジ時間 661 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//埋め込み解
#include <cstdio>
int main() {
	std::puts("urtynvwwtsgvkjpe");
	std::puts("jxvjzjihihyfamvh");
}

//以下、生成に使ったコード
//1GBのメモリだけを使い、4分以下で生成できた
#if 0
#include <cstdio>
#include <memory>
#include <cstring>
#include <cassert>

using namespace std;

struct Xor128 {
	unsigned x, y, z, w;
	Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
	unsigned operator()() {
		unsigned t = x ^ (x << 11);
		x = y; y = z; z = w;
		return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
	}
	unsigned operator()(unsigned n) { return operator()() % n; }
};

typedef unsigned long long ull;

inline ull modmult(ull x, ull y, ull MOD) {
	unsigned long long a = x, r = 0;
	while(y) {
		if(y & 1)
			if((r += a) >= MOD) r -= MOD;
		if((a += a) >= MOD) a -= MOD;
		y >>= 1;
	}
	return r;
}

inline void modadd(ull &x, ull y, ull MOD) {
	if((x += y) >= MOD) x -= MOD;
}

__forceinline void increamentHash(ull &curHash, char curString[], ull coeffZA[], ull powers[], int N, ull P, Xor128 &xor128) {
	int incPos;
	do {
		incPos = xor128() & 0xf;
	} while(incPos >= N);

	for(int i = incPos; i < N; ++ i) {
		if(curString[i] ++ == 'z') {
			curString[i] = 'a';
			modadd(curHash, coeffZA[i], P);
		} else {
			modadd(curHash, powers[i], P);
			break;
		}
	}
}

int main() {
	const ull P = 1000000000000000003ULL;
	const ull B = 123456789987654321ULL;

	const int TableBits = 28;
	const int N = 16;
	const int A = 26;
	assert(P < 1ULL << 63);
	assert(((P-1) >> TableBits) < (1ULL << 32));

	unique_ptr<unsigned[]> table(new unsigned[size_t(1) << TableBits]);
	memset(table.get(), 0, sizeof(unsigned) << TableBits);

	ull powers[N];
	powers[N - 1] = 1 % P;
	for(int i = N - 2; i >= 0; -- i)
		powers[i] = modmult(powers[i + 1], B, P);

	ull coeffZA[N];
	for(int i = 0; i < N; ++ i)
		coeffZA[i] = (P - modmult(powers[i], 'z' - 'a', P)) % P;

	char curString[N+1];
	ull initHash = 0;
	for(int i = 0; i < N; ++ i) {
		curString[i] = 'a';
		modadd(initHash, modmult(powers[i], 'a', P), P);
	}
	curString[N] = 0;

	ull curHash = initHash;
	Xor128 xor128;
	char secondString[N+1];
	ull targetHash;

	long long iter;
	size_t tableEntries = 0;
	for(iter = 0;; ++ iter) {
		if((iter & ((1U << 26) - 1)) == 0)
			fprintf(stderr, "iter = %lld, table = %lld\n",
			iter, (long long)tableEntries);

		unsigned tableIndex = curHash & ((1U << TableBits) - 1);
		unsigned tableValue = (unsigned)(curHash >> TableBits);
		unsigned t = table[tableIndex];
		if(t == 0) {
			table[tableIndex] = tableValue;
			++ tableEntries;
		} else if(t == tableValue) {
			printf("iter = %lld: %s, %llu\n", iter, curString, curHash);
			memcpy(secondString, curString, sizeof(curString));
			targetHash = curHash;
			break;
		}

		increamentHash(curHash, curString, coeffZA, powers, N, P, xor128);
	}

	curHash = initHash;
	for(int i = 0; i < N; ++ i)
		curString[i] = 'a';
	xor128 = Xor128();
	for(iter = 0;; ++ iter) {
		if(curHash == targetHash)
			break;
		increamentHash(curHash, curString, coeffZA, powers, N, P, xor128);
	}

	printf("%s\n%s\n", curString, secondString);
	fprintf(stderr, "hash = %llu\n", curHash);
	return 0;
}
#endif
0