結果

問題 No.8015 アンチローリングハッシュ
ユーザー Lay_ec
提出日時 2015-11-04 19:40:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,819 bytes
コンパイル時間 1,061 ms
コンパイル使用メモリ 102,440 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-09-13 12:26:06
合計ジャッジ時間 4,836 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <map>
#include <queue>
#include <stack>

using namespace std;

typedef long double ll;
typedef long double ld;

template <typename T1,typename T2>
ld IP(vector<vector<T1> > &B1, int x, vector<vector<T2> > &B2, int y){
	ld res=0;
	for(int i=0;i<B1.size();i++) res+=B1[i][x]*B2[i][y];
	return res;
}

//https://en.wikipedia.org/wiki/Gram-Schmidt_process
vector<vector<ld> > GS(vector<vector<ll> > &Basis){
	//vector<vector<ld> > Basis_=Basis;
	
	const int n=Basis.size();
	vector<vector<ld> > Basis_(n,vector<ld>(n));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++) Basis_[i][j]=Basis[i][j];
	}
	
	for(int i=1;i<n;i++){
		for(int j=0;j<i;j++){
			ld ip=IP(Basis,i,Basis_,j);
			ld ip2=IP(Basis_,j,Basis_,j);
			for(int k=0;k<n;k++) Basis_[k][i]-=ip/ip2*Basis_[k][j];
		}
	}
	
	return Basis_;
}

ld MU(vector<vector<ll> > &Basis,int x,vector<vector<ld> > &Basis_,int y){
	return IP(Basis,x,Basis_,y)/IP(Basis_,y,Basis_,y);
}

ld PI2(vector<vector<ll> > &Basis,vector<vector<ld> > &Basis_,int i,int x){

	const int n=Basis.size();
	vector<ld> pi(n,0);
		
	for(int j=i;j<n;j++){
		ld ip1=IP(Basis,x,Basis_,j);
		ld ip2=IP(Basis_,j,Basis_,j);
		
		for(int k=0;k<n;k++){
			pi[k]+=ip1/ip2*Basis_[k][j];
		}
	}
	
	ld res=0;
	for(int j=0;j<n;j++) res+=pi[j]*pi[j];
	return res;
	
}

vector<ll> LLL(vector<vector<ll> > Basis){
	const int n=Basis.size();
	const ld delta=(1.0/4.0)+powl(3.0/4.0,(ld)n/(ld)(n-1));
	vector<ll> svp(n);
		
	vector<vector<ld> > Basis_=GS(Basis);
	while(true){
/*
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) cout<<Basis[i][j]<<" ";
			cout<<endl;
		}
*/
		
		for(int i=0;i<n;i++){
			for(int j=i-1;j>=0;j--){
				ll c_ij=roundl(IP(Basis,i,Basis,j)/IP(Basis,j,Basis,j));
				for(int k=0;k<n;k++) Basis[k][i]-=c_ij*Basis[k][j];
			}
		}
		Basis_=GS(Basis);
		
		bool cont=false;
		for(int i=0;i<n-1;i++){
			ld p1=PI2(Basis,Basis_,i,i);
			ld p2=PI2(Basis,Basis_,i,i+1);
			if(delta*p1>p2){
				for(int j=0;j<n;j++) swap(Basis[j][i],Basis[j][i+1]);
				Basis_=GS(Basis);
				cont=true;
				break;
			}	
		}
		
		if(cont) continue;
		else{
/*			
			cout<<"result"<<endl;
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					cout<<Basis[i][j]<<" ";
				}
				cout<<endl;
			}
*/
			for(int i=0;i<n;i++) svp[i]=Basis[i][0];
			return svp;
		}
		
				
	}
	
}

unsigned long long get_hash(string s, unsigned long long a, unsigned long long b){
	unsigned long long hash = 0;

	for(int i = 0; i < s.size(); i++){
		hash = (hash * a + s[i]) % b;
	}

	return hash;
}

int main(){

/*
	//http://grampus.jaist.ac.jp/hiss/lattice/091109-revise.pdf
	vector<vector<ll> > mat(3,vector<ll>(3));
	mat[0][0]=4;  mat[1][0]=1;  mat[2][0]=2;
	mat[0][1]=4;  mat[1][1]=7; mat[2][1]=2;
	mat[0][2]=3;  mat[1][2]=1; mat[2][2]=7;

	LLL(mat);
*/
	

	ll p,b;
	cin>>p>>b;
	swap(p,b); //No.3015
	vector<ll> coe;
	int n;
	for(n=4;;n+=4){
		//cout<<n<<endl;
		vector<vector<ll> > Basis(n,vector<ll>(n,0));
		for(int i=0;i<n-1;i++){
			Basis[i][i]=-b;
			Basis[i+1][i]=1;
		}
		Basis[0][n-1]=p;
		
		coe=LLL(Basis);
		reverse(coe.begin(),coe.end());
		
		bool ok=true;
		for(int i=0;i<n;i++) ok&=(abs(coe[i])<=25);
		if(ok){
/*
			for(int i=0;i<n;i++) cout<<coe[i]<<" ";
			cout<<endl;
*/
			break;
		}
	}

	map<int,pair<char,char> > st;
	for(int i=-25;i<=25;i++){
		bool ok=false;
		for(char s='a';s<='z' && !ok;s++){
			for(char t='a';t<='z' && !ok;t++){
				if(s-t==i){
					st[i]=make_pair(s,t);
					ok=true;
				}
			}
		}
	}

	string s,t;
	for(int i=0;i<n;i++){
		s+=st[coe[i]].first;
		t+=st[coe[i]].second;
	}
	cout<<s+"\n"<<t<<endl;
	//cout<<get_hash(s,b,p)<<endl;
	//cout<<get_hash(t,b,p)<<endl;

	return 0;

}
0