結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー IL_msta
提出日時 2015-11-01 06:52:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 6,501 bytes
コンパイル時間 2,469 ms
コンパイル使用メモリ 113,112 KB
実行使用メモリ 30,880 KB
最終ジャッジ日時 2024-09-13 06:49:21
合計ジャッジ時間 13,831 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
 
#include <iostream>
#include <iomanip>
#include <sstream>
 
#include <algorithm>
#include <cmath>
 
#include <string>
#include <queue>
#include <vector>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <valarray>

//#include <random>//xAOJ
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
 
#define PII pair<int,int>
/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
/////////
using namespace::std;
/////////
/////////

inline long double dot(const valarray<long double>& A,const valarray<long double>& B ){
	return ( A * B ).sum();
}

inline long double norm(valarray<long double> &A ){
	return sqrt( (A * A).sum() );
}

//簡約ステップ
/*
入力 行列g g[i] = 基底 b_i
出力
	r 簡約したもの
	u μ(i,j) := <b_i,b_j*>/<b_j*,b_j*>  :(i>j)
	グラムシュミット係数
	この係数を簡約で1/2以下にしていく
	二等辺三角形、垂線底辺を２分する
*/
/*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]) / dot(r[j],r[j]);
		}
        r[i] = g[i];
        for(int j = 0; j < i; ++ j){
            r[i] = r[i] - u[i][j] * r[j];
		}
    }
}
*/
//グラムシュミット直交化ベクトルを計算
//Gram-Schmidt orthonormalization
//つまりcomputeGSO
void GSO(const vector< valarray<long double> > &B,
	vector< valarray<long double> >& Bstar,
	vector< valarray<long double> >& myu
	){
	
	int N = B.size();

	//半分計算する
	for(int i=0;i<N;++i){
		for(int j=0;j<i;++j){
			myu[i][j] = dot( B[i],Bstar[j] ) / dot( Bstar[j],Bstar[j] );
			//
		}
		Bstar[i] = B[i];
		for(int j=0;j<i;++j){
			Bstar[i] -= myu[i][j] * Bstar[j];
		}
	}
}

vector< valarray<long double> > LLL(vector< valarray<long double> >& inB){
	//B B[i]が基底b_i
	//long double delta = 0.5;//
	int N = inB.size();//基底の数
	int M = 0;//基底の次元(要素数)
	if( N > 0){
		M = inB[0].size();
	}
	
	//グラムシュミット直交化 ベクトル Bstar[i]
	vector< valarray<long double> > B(N,valarray<long double>(M) );
	B = inB;
	vector< valarray<long double> > Bstar(N,valarray<long double>(M) );
	vector< valarray<long double> > myu(N,valarray<long double>(N) );
	//GSO(B,Bstar,myu);
	bool flag = true;
	for(;flag;){
		flag = false;
		GSO(B,Bstar,myu);
		int i=1;
		while( i < N ){
			for(int j=i-1; j>=0; --j){
				/*if(  dot( B[i]-B[j],B[i]-B[j] ) < dot( B[i],B[i] ) ){
					B[i] = B[i]-B[j];
					flag = true;
				}*/
				if( abs( myu[i][j] ) > 0.5 ){
					long double keisuu = floor( myu[i][j] +0.5);//切り下げ関数
					B[i] = B[i] - keisuu * B[j];
					myu[i][j] -= keisuu;
					
					long long cZ = (long long)keisuu;
					for(int k=0;k<N;++k){
						inB[i][k] = (LL)inB[i][k] - cZ * (LL)inB[j][k];
					}
					GSO(B,Bstar,myu);
				}
			}
			/*
			|bi*|^2 >= (3/4 - μ(i,i-1)^2 )|b(i-1)|^2
			*/
			
			if( dot( Bstar[i],Bstar[i])  <
				((long double)3.0/4.0 - myu[i][i-1]*myu[i][i-1])*
				dot(Bstar[i-1],Bstar[i-1]) )
			
			/*if( dot(Bstar[i-1],Bstar[i-1]) >
				dot(Bstar[i],Bstar[i])*4 )
			*/
			{
				swap( B[i-1], B[i] );
				swap( inB[i-1], inB[i] );
				GSO(B,Bstar,myu);
				i = max( i-1, 1);
			}else{
				++i;
			}
		}
	}
	/*for(int i=0;i<N;++i){
		for(int j=0;j<M;++j){
			cout << " " << B[i][j];
		}cout << endl;
	}*/
	return B;
}

LL inP,inB;
vector< vector<ULL> > bmp(26,vector<ULL>(100001) );

ULL kake(ULL A, int n){
	//A*n
	ULL ret=0;
	for(int bit=31;bit>=0;--bit){
		ret = (ret + ret) % inP;
		if( n & (1 << bit) ){
			ret = (ret + A) % inP;
		}
	}
	return ret;
}
void initbmp(){
	bmp[0][0] = 1;
	bmp[0][1] = inB % inP;
	for(int i=2;i<100001;++i){
		bmp[0][i] = ( bmp[0][i-1] * inB ) % inP;
	}
	ULL add;
	for(int i=0;i<100001;++i){
		add = bmp[0][i];
		bmp[0][i] = kake( bmp[0][i], 97  );
		for(int j=1;j<26;++j){
			bmp[j][i] = ( bmp[j-1][i] + add ) % inP;
		}
	}
}
ULL calH(string &str){
	int len = str.size();
	ULL ret = 0;
	for(int i=0;i<len;++i){
		ret = ( ret + bmp[str[i]-'a'][len-i-1] ) % inP;
	}
	return ret;
}
LL calH( vector<int> &v ){
	int len = v.size();
	LL ret = 0;
	for(int i=0;i<len;++i){
		ret = ( ret + bmp[ v[i] ][len-i-1] );
		if( ret >= inP ){
			ret = ret % inP;
		}
	}
	return ret;
}
void show( vector<int> &v ){
	char c;
	int len = v.size();
	for(int i=0;i<len;++i){
		c = v[i] + 'a';
		cout << c;
	}
	cout << '\n';
	return;
}

void solve(){
	/*vector< valarray<long double> > B(3,valarray<long double>(3));
	B[0][0] = 1;
	B[0][1] = 1;
	B[0][2] = 1;
	B[1][0] = -1;
	B[1][1] = 0;
	B[1][2] = 2;
	B[2][0] = 3;
	B[2][1] = 5;
	B[2][2] = 6;
	B = LLL(B);
	for(int i=0;i<3;++i){
		for(int j=0;j<3;++j){
			cout << " " << B[i][j];
		}cout << endl;
	}
	// 0 1 0
	// 1 0 1
	//-1 0 2
	return;*/
	cin >> inP >> inB;
	initbmp();
	const int Alpha = 26;
	int n;
	vector<int> ans;
	bool flag;
	n = 16;//
	for(;;){
		for(;;n+=4){
//			cout << n << endl;
			vector< valarray<long double> > B(n,valarray<long double>(n) );
			vector< valarray<long double> > getB(n,valarray<long double>(n) );
			for(int i=0;i<n;++i){
				for(int j=0;j<n;++j){
					B[i][j] = 0;
				}
			}
			for(int i=0;i< n-1;++i){
				B[i][i+0] = (long double)(-inB);
				B[i][i+1] = 1;
			}
			B[n-1][0] = (long double)inP;

			//LLL
			//getB = LLL( B );
			B = LLL( B );
//			cout << B[0][0] << endl;
			for(int asd=0;asd<n;++asd){
				flag = true;
				for(int i=0;i<n;++i){
					flag &= abs( B[asd][i] ) < Alpha;
				}
				if( flag ){
					ans.resize( n );
					for(int i=0;i<n;++i){
						ans[i] = (int)B[asd][i];
					}
				}else{
					continue;
				}

				int len = n;
				while( len > 1 && ans[len-1] == 0 ){
					--len;//reading 0
				}
				string S(len,'a');
				string T(len,'a');
				int temp;
				for(int i=0;i<len;++i){
					temp = ans[len-1 -i];
					if( temp >= 0 ){
						//S[i]-T[i] = temp;
						S[i] = 'a' + temp;
						T[i] = 'a';
					}else{
						S[i] = 'a';
						T[i] = 'a' - temp;
					}
				}
				ULL SH,TH;
				SH = calH( S );
				TH = calH( T );
//				cout << SH << " " << TH << endl;
//				cout << S << endl;
//				cout << T << endl;
				if( SH == TH ){
					cout << S << endl;
					cout << T << endl;
					return;
				}
			}
		}//for(n=16;;n+=4)		
	}
}

int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    cout << setprecision(16);//
	
	//cpp
	solve();
	return 0;
}
0