結果

問題 No.3015 アンチローリングハッシュ
ユーザー IL_mstaIL_msta
提出日時 2015-11-01 07:20:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 97 ms / 2,000 ms
コード長 6,855 bytes
コンパイル時間 1,496 ms
コンパイル使用メモリ 114,316 KB
実行使用メモリ 24,192 KB
最終ジャッジ日時 2024-09-13 06:49:40
合計ジャッジ時間 4,424 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
24,192 KB
testcase_01 AC 92 ms
24,064 KB
testcase_02 AC 89 ms
24,064 KB
testcase_03 AC 89 ms
24,064 KB
testcase_04 AC 91 ms
23,936 KB
testcase_05 AC 89 ms
24,064 KB
testcase_06 AC 94 ms
24,064 KB
testcase_07 AC 89 ms
24,192 KB
testcase_08 AC 95 ms
23,936 KB
testcase_09 AC 95 ms
24,192 KB
testcase_10 AC 96 ms
24,192 KB
testcase_11 AC 97 ms
24,064 KB
testcase_12 AC 96 ms
23,936 KB
testcase_13 AC 94 ms
24,064 KB
testcase_14 AC 95 ms
24,064 KB
testcase_15 AC 94 ms
23,936 KB
testcase_16 AC 96 ms
23,936 KB
testcase_17 AC 95 ms
23,936 KB
testcase_18 AC 96 ms
23,936 KB
testcase_19 AC 95 ms
23,936 KB
testcase_20 AC 95 ms
24,192 KB
testcase_21 AC 96 ms
24,064 KB
testcase_22 AC 89 ms
24,064 KB
権限があれば一括ダウンロードができます

ソースコード

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> >& BBB){
	//B B[i]が基底b_i
	//long double delta = 0.5;//
	int N = BBB.size();//基底の数
	int M = 0;//基底の次元(要素数)
	if( N > 0){
		M = BBB[0].size();
	}
	
	//グラムシュミット直交化 ベクトル Bstar[i]
	vector< valarray<long double> > B(N,valarray<long double>(M) );
	B = BBB;
	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){
						BBB[i][k] = (LL)BBB[i][k] - cZ * (LL)BBB[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( BBB[i-1], BBB[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;
}

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;
}

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 >> inB >> inP;
	int AA,BB;
	AA = inB;
	BB = inP;

	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,aH,bH;
				SH = calH( S );
				TH = calH( T );
				aH = get_hash(S,AA,BB);
				bH = get_hash(T,AA,BB);
//				cout << SH << " " << TH << endl;
//				cout << S << endl;
//				cout << T << endl;
				if( SH == TH ){
					cout << S << endl;
					cout << T << endl;
//					cout << aH << endl;
//					cout << bH << 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