結果

問題 No.3014 多項式ハッシュに関する教育的な問題
ユーザー IL_mstaIL_msta
提出日時 2015-10-29 15:10:06
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,293 bytes
コンパイル時間 1,146 ms
コンパイル使用メモリ 103,492 KB
実行使用メモリ 31,008 KB
最終ジャッジ日時 2024-09-13 04:32:05
合計ジャッジ時間 13,828 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
権限があれば一括ダウンロードができます

ソースコード

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 <random>

/////////
#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;
/////////
/////////
ULL P,B;
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) % P;
		if( n & (1 << bit) ){
			ret = (ret + A) % P;
		}
	}
	return ret;
}
void initbmp(){
	bmp[0][0] = 1;
	bmp[0][1] = B % P;
	for(int i=2;i<100001;++i){
		bmp[0][i] = ( bmp[0][i-1] * B ) % P;
	}
	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 ) % P;
		}
	}
}
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] ) % P;
	}
	return ret;
}
ULL calH( vector<int> &v ){
	int len = v.size();
	ULL ret = 0;
	for(int i=0;i<len;++i){
		//if( 0 <= v[i] && v[i] < 26 )
		{
			//ret = ( ret + bmp[ v[i] ][len-i-1] ) % P;
			ret = ( ret + bmp[ v[i] ][len-i-1] );
			if( ret >= P ){
				ret = ret % P;
			}
		}
	}
	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(){
	
	cin >> P >> B;
	initbmp();
	ULL ah,bh;

	const int Lmax = 10000;
	vector<int> S(Lmax,0);
	vector<int> T(Lmax,0);

	random_device rnd;
	mt19937 mt(rnd());
	for(int i=0;i<Lmax;++i){
		S[i] = (mt()%26 + 26 )%26;
	}
	ah = calH( S );

	int i=0;
	show( S );
	for(;;){
		for(int i=0;i<Lmax;++i){
			//T[i] = (mt()%26 + 26 ) % 26;
			T[i] = mt()%26;
		}
		bh = calH( T );
		if( ah == bh ){
			break;
		}else{
			//cout << "x";
		}
	}
	show( T );
}

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