結果

問題 No.599 回文かい
コンテスト
ユーザー Daylight
提出日時 2022-08-27 09:58:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 246 ms / 4,000 ms
コード長 4,487 bytes
コンパイル時間 4,486 ms
コンパイル使用メモリ 258,732 KB
最終ジャッジ日時 2025-01-31 06:13:38
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define SZ(x) (int) (x).size()
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REPR(i, n) for(int i = (n) -1; i >= 0; i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase(unique(ALL(v)), (v).end())

typedef long long unsigned int llu;
//typedef long long ll;
typedef vector<int> vi;
//typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 29);
//const ll LINF = 1e18;
const double PI = acos(-1);

template<typename T>
vector<T> make_v(size_t a) {
	return vector<T>(a);
}

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(
		a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(
	T& t, const V& v) {
	t = v;
}

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(
	T& t, const V& v) {
	for(auto& e: t) fill_v(e, v);
}

template<class T>
bool chmax(T& a, const T& b) {
	if(a < b) {
		a = b;
		return true;
	}
	return false;
}

template<class T>
bool chmin(T& a, const T& b) {
	if(a > b) {
		a = b;
		return true;
	}
	return false;
}

template<typename S, typename T>
istream& operator>>(istream& is, pair<S, T>& p) {
	cin >> p.first >> p.second;
	return is;
}

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	for(T& x: vec) is >> x;
	return is;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i, SZ(vec)) {
		if(i != 0) os << " ";
		os << vec[i];
	}
	return os;
}
#include <atcoder/all>
using namespace atcoder;
struct RollingHash {
	static const uint64_t mod = (1ull << 61ull) - 1;
	using uint128_t = __uint128_t;
	uint64_t base1, base2;
	vector<uint64_t> pow1, pow2;

	RollingHash() {
		mt19937_64 mt(chrono::steady_clock::now()
						  .time_since_epoch()
						  .count());
		uniform_int_distribution<uint64_t> rand(
			1e9, RollingHash::mod - 1);
		base1 = rand(mt);
		base2 = rand(mt);
		pow1.push_back(1);
		pow2.push_back(1);
	}

	// 必要分のpow配列を追加で求める。
	inline void expand(int sz) {
		int pre_sz = SZ(pow1);
		if(pre_sz < sz + 1) {
			for(int i = pre_sz - 1; i < sz; i++) {
				pow1.push_back(mul(pow1[i], base1));
				pow2.push_back(mul(pow2[i], base2));
			}
		}
	}
	pair<vector<uint64_t>, vector<uint64_t>> build(
		const string& s) {
		expand(SZ(s) + 1);
		vector<uint64_t> hash1
			= vector<uint64_t>(SZ(s) + 1);
		vector<uint64_t> hash2
			= vector<uint64_t>(SZ(s) + 1);
		REP(i, SZ(s)) {
			hash1[i + 1] = add(mul(hash1[i], base1), s[i]);
			hash2[i + 1] = add(mul(hash2[i], base2), s[i]);
		}
		return { hash1, hash2 };
	}

	template<typename T>
	pair<vector<uint64_t>, vector<uint64_t>> build(
		const vector<T>& s) {
		expand(SZ(s) + 1);
		vector<uint64_t> hash1
			= vector<uint64_t>(SZ(s) + 1);
		vector<uint64_t> hash2
			= vector<uint64_t>(SZ(s) + 1);
		REP(i, SZ(s)) {
			hash1[i + 1] = add(mul(hash1[i], base1), s[i]);
			hash2[i + 1] = add(mul(hash2[i], base2), s[i]);
		}
		return { hash1, hash2 };
	}

	pair<uint64_t, uint64_t> query(
		const pair<vector<uint64_t>, vector<uint64_t>>&
			hash,
		int begin, int length) {
		assert(begin + length <= SZ(hash.first));
		assert(begin >= 0);
		assert(length > 0);
		expand(length);
		return {
			add(hash.first[begin + length],
				mod - mul(hash.first[begin], pow1[length])),
			add(hash.second[begin + length],
				mod - mul(hash.second[begin], pow2[length]))
		};
	}

	static inline uint64_t add(uint64_t a, uint64_t b) {
		if((a += b) >= mod) a -= mod;
		return a;
	}

	static inline uint64_t mul(uint64_t a, uint64_t b) {
		uint128_t c = (uint128_t) a * b;
		return add(c >> 61, c & mod);
	}
};
using mint = modint1000000007;
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	int N = SZ(S);
	RollingHash rh;
	auto hash = rh.build(S);
	auto dp = make_v<mint>(N + 1);
	dp[0] = 1;
	mint ans(0);
	FOR(lr, 1, N + 1) {
		REP(ll, lr) {
			int rr = N - ll;
			int rl = N - lr;
			if(ll == rl && lr == rr) {
				ans += dp[ll];
			}
			if(lr > rl) continue;
			int len = lr - ll;
			if(rh.query(hash, ll, len)
			   != rh.query(hash, rl, len))
				continue;
			dp[lr] += dp[ll];
			if(lr == rl) {
				ans += dp[ll];
			}
		}
	}
	cout << ans.val() << endl;
	return 0;
}
0