結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー eto_nagisa
提出日時 2018-12-20 09:31:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,403 bytes
コンパイル時間 498 ms
コンパイル使用メモリ 63,136 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-09-25 08:24:29
合計ジャッジ時間 1,057 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
#include <iostream>
#include <cassert>

using namespace std;
using namespace NTL;

// compute (a*b)%mod within long long range
long long mult(long long a, long long b, long long mod) {
	long long ret = 0;
	long long val = a % mod;
	while (b) {
		if (b & 1) {
			ret += val;
			if (ret > mod)ret -= mod;
		}
		val <<= 1;
		if (val > mod)val -= mod;
		b >>= 1;
	}
	return ret;
}

// hash(s) := sum_i(s[i]*base^(s.length-i-1) mod m
long long rolling_hash(string s, long long mod, long long base) {
	long long ret = 0;
	for (int i = 0; i < s.size(); ++i) {
		ret = mult(ret, base, mod);
		ret += s[i] - 'a' + 1;
		ret %= mod;
	}
	return ret;
}
// hash(s) := sum_i(s[i]*base^i mod m
long long rolling_hash_rev(string s, long long mod, long long base) {
	long long ret = 0;
	for (int i = s.size() - 1; i >= 0; --i) {
		ret = mult(ret, base, mod);
		ret += s[i] - 'a' + 1;
		ret %= mod;
	}
	return ret;
}

mat_ZZ init_mat(int n, long long mod, long long base) {
	mat_ZZ b(INIT_SIZE, n, n);
	for (int i = 0; i < n - 1; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j) b[i][j] = -base;
			else if (i + 1 == j) b[i][j] = 1;
			else b[i][j] = 0;
		}
	}
	b[n - 1][0] = mod;
	for (int i = 1; i < n; ++i) {
		b[n - 1][i] = 0;
	}
	return b;
}

//call calc with rev = true when the definition of rolling hash algorithms is
// hash(s) := sum_i(s[i] * base ^ i) mod m
bool calc(mat_ZZ b, long long mod, long long base, bool rev = false) {
	ZZ det;
	LLL(det, b);
	vec_ZZ vec = b[0];
	bool ok = true;
	int alpha_size = 26;
	for (int i = 0; i < vec.length(); ++i) {
		if (abs(vec[i]) >= alpha_size)ok = false;
	}
	if (!ok)return false;
	string s, t;
	for (int i = 0; i < vec.length(); ++i) {
		if (vec[i] <= 0) {
			s += 'a';
			t += char('a' - to_long(vec[i]));
		}
		else {
			s += char('a' + to_long(vec[i]));
			t += 'a';
		}
	}
	if (!rev) {
		reverse(s.begin(), s.end());
		reverse(t.begin(), t.end());
		assert(rolling_hash(s, mod, base) == rolling_hash(t, mod, base));
	}
	else {
		assert(rolling_hash_rev(s, mod, base) == rolling_hash_rev(t, mod, base));
	}
	cout << s << "\n" << t << endl;
	return true;

}



int main()
{
	long long mod, base;
	cin >> mod >> base;
	for (int n = 4; n <= 2048; n += 4) {
		mat_ZZ b = init_mat(n, mod, base);
		if (calc(b, mod, base))return 0;
		
	}
}
*/

#include <iostream>

using namespace std;
int main(){
    cout<<"guhaafmeiaab"<<endl;
    cout<<"aaancaaaabda"<<endl;
}
0