結果

問題 No.8015 アンチローリングハッシュ
ユーザー koyumeishi
提出日時 2015-10-30 23:56:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,811 bytes
コンパイル時間 1,441 ms
コンパイル使用メモリ 106,824 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-13 06:10:51
合計ジャッジ時間 2,389 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 3014用に書いていたのでぐちゃぐちゃ


#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

template<class T>
ostream& operator << (ostream& os, vector<T> vec){
	for(int i=0; i<vec.size(); i++){
		os << (long long)vec[i] << endl;
	}
	return os;
}

long long get_hash(long long p, long long b, string& s){
	__int128 hash_s = 0;
	__int128 bk = 1;
	for(int i=0; i<s.size(); i++){
		hash_s = (hash_s*b + s[i])%p;
	}
	return (long long)hash_s;
}

#include <random>
#include <ctime>

/*

case:

1000000000000000003 123456789987654321


*/

class solver{
	const long long p,b;
	const long long _p_, _b_;
	vector<__int128> v;
	vector<__int128> w;
	vector<int> pos_shuffled;
	mt19937 mt;
	string s,t;
	int seed;
	static constexpr int len = 100;
	static constexpr int len__ = 100;


	bool solve_vec(){
		vector<long long> c(len, 0);
		__int128 val = 0;
		__int128 hash = 0;


		bool ok = false;
		long long unko_seed = mt();
		mt19937 my_mt(unko_seed);

		uniform_int_distribution<int> pos(0, len__-1);
		uniform_int_distribution<int> alf(0, 25);

		map<long long, long long> memo;

		for(int i=0; i<len; i++){
			int at = i;
			int ch = alf(my_mt);
			val = (val + ((ch - c[at])*v[at])%p + p) % p;
			hash = (hash + ((ch - c[at])*w[at])%_p_ + _p_) % _p_;
			c[at] = ch;
		}

		long long cnt = 0;

		while(!ok && cnt<1e7){
			int at = pos_shuffled[pos(my_mt)];
			int ch = alf(my_mt);

			val = (val + ((ch - c[at])*v[at])%p + p) % p;
			hash = (hash + ((ch - c[at])*w[at])%_p_ + _p_) % _p_;
			c[at] = ch;

			auto itr = memo.find( val );
			if(itr!=memo.end() && hash != itr->second){
				ok = true;
				my_mt = mt19937(unko_seed);

				//cerr << (long long) val << " " << (long long)hash << endl;

				vector<long long> d(len, 0);
				hash = 0;
				val = 0;

				for(int i=0; i<len; i++){
					int at = i;
					int ch = alf(my_mt);
					val = (val + ((ch - d[at])*v[at])%p + p) % p;
					hash = (hash + ((ch - d[at])*w[at])%_p_ + _p_) % _p_;
					d[at] = ch;
				}

				while(hash != itr->second || val != itr->first){
					int at = pos_shuffled[pos(my_mt)];
					int ch = alf(my_mt);

					val = (val + ((ch - d[at])*v[at])%p + p) % p;
					hash = (hash + ((ch - d[at])*w[at])%_p_ + _p_) % _p_;
					d[at] = ch;
				}
				//cerr << (long long) val << " " << (long long)hash << endl;

				for(int i=0; i<len; i++){
					s[i] = 'a'+c[i];
				}

				for(int i=0; i<len; i++){
					t[i] = 'a'+d[i];
				}

				return s != t;

			}else if(memo.size()<1e6){
				memo[val] = hash;
			}

			cnt++;
		}
		return ok;
	}

public:
	solver(long long p_, long long b_):
	  p(p_) , b(b_), s(len, 'a'), pos_shuffled(len), _p_(1000000000000000009LL), _b_(1000000009LL)
	{
		//initialize
		srand((unsigned)time(NULL));
		seed = (unsigned)time(NULL);

		mt = mt19937(seed);

		iota(pos_shuffled.begin(), pos_shuffled.end(), 0);
		//shuffle(pos_shuffled.begin(), pos_shuffled.end(), mt);
		reverse(pos_shuffled.begin(), pos_shuffled.end());

		__int128 bk = 1;
		for(int i=0; i<s.size(); i++){
			v.push_back((long long)bk);
			bk = (bk*b)%p;
		}

		bk = 1;
		for(int i=0; i<s.size(); i++){
			w.push_back((long long)bk);
			bk = (bk*_b_)%_p_;
		}

		t = s;
	}

	void unko(){
		//bool ok = my_rand();
		bool ok = false;
		long long cnt = 0;
		while(!ok) {
			//cerr << "run : " << cnt++ << endl;
			ok = solve_vec();

			reverse(s.begin(), s.end());
			reverse(t.begin(), t.end());

			cout << s << endl;
			cout << t << endl;

			// cerr << get_hash(p,b, s) << endl;
			// cerr << get_hash(p,b, t) << endl;

			// cerr << (ok?"OK":"NO") << endl;
			// cerr << seed << endl;
		}
	}

};


int main(){
	long long p,b;
	cin >> b >> p;

	solver x(p,b);
	x.unko();


	return 0;
}
0