test/ABC284f.test.cpp

• View this file on GitHub
• Last update: 2023-01-18 06:37:34+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc284/submissions/38126429

Depends on

• rollinghash (ロリハ) (src/string/rollinghash.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/string/rollinghash.hpp"

#include <iostream>
#include <string>
#include <algorithm>

int main() {
	// int n; std::cin >> n;
	// std::string t; std::cin >> t;
	// std::string r = t;
	// std::reverse(r.begin(), r.end());
	// zawa::rollinghash<1000000> roll;
	// auto rht = roll.build(t);
	// auto rhr = roll.build(r);
	// for (int i = 0 ; i < n ; i++) {
	// 	auto f = roll.hash(rht, 0, i);
	// 	auto c = roll.hash(rhr, n - i, 2 * n - i);
	// 	auto b = roll.hash(rht, i + n, 2 * n);
	// 	auto cc = roll.concate(f, b);
	// 	if (c == cc) {
	// 		std::cout << r.substr(n - i, n) << std::endl;
	// 		std::cout << i << std::endl;
	// 		return 0;
	// 	}
	// }
	// std::cout << -1 << std::endl;
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 284 - F ABCBAC
 * https://atcoder.jp/contests/abc284/submissions/38126429
 */

#line 1 "test/ABC284f.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/string/rollinghash.hpp"

#include <random>
#include <iostream>
#include <algorithm>
#include <string>

namespace zawa {

template <std::size_t max_length>
class rollinghash {
private:
	using hash_type = long long;

	std::random_device seed_gen;
	std::mt19937_64 mt;
	hash_type base;
	const hash_type mod = (1ULL << 61ULL) - 1;
	std::vector<hash_type> pows;

public:

	struct info {
		std::size_t len;
		hash_type hash;
		info() : len(0), hash(0) {}
		bool operator==(const info& a) {
			return len == a.len and hash == a.hash;
		}
	};

	rollinghash() : mt(seed_gen()), pows(max_length + 1, 1LL) {
		base = std::clamp((hash_type)mt() % mod, (hash_type)1e9, mod - 1);
		for (std::size_t i = 0 ; i < max_length ; i++) {
			pows[i + 1] = ((__int128_t)pows[i] * base) % mod;
		}
	}

	template <class T>
	std::vector<info> build(const std::vector<T>& A) {
		std::vector<info> res(A.size() + 1, info());	
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			res[i + 1].len = i + 1;
			res[i + 1].hash = ((__int128_t)base * res[i].hash + (__int128_t)A[i]) % mod;
		}
		return res;
	}

	std::vector<info> build(const std::string& s) {
		return build(std::vector(s.begin(), s.end()));
	}

	info hash(const std::vector<info>& H, int l, int r) {
		info res = H[r];
		res.len -= H[l].len;
		res.hash -= ((__int128_t)H[l].hash * pows[r - l]) % mod;
		if (res.hash < 0) {
			res.hash += mod;
		}
		return res;
	}

	info concate(const info& h1, const info& h2) { 
		info res;
		res.len = h1.len + h2.len;
		res.hash = ((((__int128_t)h1.hash * pows[h2.len]) % mod) + h2.hash) % mod;
		return res;
	}

};

} // namespace zawa
#line 4 "test/ABC284f.test.cpp"

#line 8 "test/ABC284f.test.cpp"

int main() {
	// int n; std::cin >> n;
	// std::string t; std::cin >> t;
	// std::string r = t;
	// std::reverse(r.begin(), r.end());
	// zawa::rollinghash<1000000> roll;
	// auto rht = roll.build(t);
	// auto rhr = roll.build(r);
	// for (int i = 0 ; i < n ; i++) {
	// 	auto f = roll.hash(rht, 0, i);
	// 	auto c = roll.hash(rhr, n - i, 2 * n - i);
	// 	auto b = roll.hash(rht, i + n, 2 * n);
	// 	auto cc = roll.concate(f, b);
	// 	if (c == cc) {
	// 		std::cout << r.substr(n - i, n) << std::endl;
	// 		std::cout << i << std::endl;
	// 		return 0;
	// 	}
	// }
	// std::cout << -1 << std::endl;
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 284 - F ABCBAC
 * https://atcoder.jp/contests/abc284/submissions/38126429
 */

Back to top page