結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー anta
提出日時 2015-10-20 03:01:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 2,407 bytes
コンパイル時間 1,014 ms
コンパイル使用メモリ 87,424 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-07-22 10:59:27
合計ジャッジ時間 1,459 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <valarray>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;

typedef long double R;
typedef valarray<R> VecR;
typedef vector<VecR> MatR;

inline R dot(const VecR &x, const VecR &y) {
	return (x * y).sum();
}

inline R norm(const VecR &x) {
	return dot(x, x);
}

void computeGSO(const MatR &g, MatR &r, MatR &u) {
	int n = g.size();
	for(int i = 0; i < n; ++ i) {
		for(int j = 0; j < i; ++ j)
			u[i][j] = dot(g[i], r[j]) / norm(r[j]);
		r[i] = g[i];
		for(int j = 0; j < i; ++ j)
			r[i] -= u[i][j] * r[j];
	}
}

void basisReduction(vector<vector<long long> > &f) {
	int n = f.size();
	MatR g(n), r(n), u(n);
	for(int i = 0; i < n; ++ i) {
		assert(f[i].size() == n);
		g[i].resize(n);
		for(int j = 0; j < n; ++ j)
			g[i][j] = (R)f[i][j];
		r[i].resize(n);
		u[i].resize(i);
	}
	computeGSO(g, r, u);
	for(int i = 1; i < n; ) {
		for(int j = i-1; j >= 0; -- j) {
			if(abs(u[i][j]) < .5) continue;
			R c = floor(u[i][j] + .5);
			g[i] -= c * g[j];
			long long cZ = (long long)c;
			for(int k = 0; k < n; ++ k)
				f[i][k] -= cZ * f[j][k];
			computeGSO(g, r, u);
		}
		if(i > 0 && norm(r[i-1]) > norm(r[i]) * 2) {
			swap(g[i-1], g[i]);
			swap(f[i-1], f[i]);
			computeGSO(g, r, u);
			-- i;
		}else {
			++ i;
		}
	}
}

long long calcHash(const string &S, long long P, long long B) {
	long long h = 0;
	for(int i = 0; i < (int)S.size(); ++ i)
		h = ((__int128)h * B + S[i]) % P;
	return h;
}

int main() {
	assert(sizeof(long double) >= 10);
	const int Alphas = 26;
	long long P, B;
	while(cin >> P >> B) {
		int n;
		vector<int> poly;
		for(n = 16;; n += 4) {
			vector<vector<long long> > L(n, vector<long long>(n, 0));
			for(int i = 0; i < n - 1; ++ i) {
				L[i][i + 0] = -B;
				L[i][i + 1] = 1;
			}
			L[n - 1][0] = P;
			basisReduction(L);

			bool ok = true;
			for(int i = 0; i < n; ++ i)
				ok &= abs(L[0][i]) < Alphas;
			if(ok) {
				poly.resize(n);
				for(int i = 0; i < n; ++ i)
					poly[i] = (int)L[0][i];
				break;
			}
		}

		int len = n;
		while(len > 1 && poly[len - 1] == 0) -- len;

		string S(len, '?'), T(len, '?');
		for(int i = 0; i < len; ++ i) {
			int a = poly[len - 1 - i];
			if(a >= 0) {
				S[i] = 'a' + a;
				T[i] = 'a';
			} else {
				S[i] = 'a';
				T[i] = 'a' - a;
			}
		}

		assert(calcHash(S, P, B) == calcHash(T, P, B));

		cout << S << endl;
		cout << T << endl;
	}
	return 0;
}
0