結果

問題 No.599 回文かい
ユーザー Jumbo_kpr
提出日時 2019-08-01 15:14:50
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 146 ms
コード長 3,278 Byte
コンパイル時間 707 ms
使用メモリ 8,920 KB
最終ジャッジ日時 2019-10-23 02:31:13

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0_0.txt AC 3 ms
8,916 KB
0_1.txt AC 3 ms
6,876 KB
0_2.txt AC 3 ms
6,872 KB
0_3.txt AC 3 ms
6,876 KB
1_0.txt AC 3 ms
6,872 KB
1_1.txt AC 3 ms
6,872 KB
1_2.txt AC 3 ms
6,872 KB
1_3.txt AC 3 ms
6,872 KB
1_4.txt AC 3 ms
8,920 KB
1_5.txt AC 3 ms
6,876 KB
2_0.txt AC 3 ms
6,876 KB
2_1.txt AC 4 ms
6,872 KB
2_2.txt AC 4 ms
6,876 KB
2_3.txt AC 5 ms
6,872 KB
2_4.txt AC 95 ms
6,872 KB
2_5.txt AC 9 ms
6,872 KB
2_6.txt AC 129 ms
6,876 KB
2_7.txt AC 146 ms
6,876 KB
3_0.txt AC 4 ms
6,872 KB
3_1.txt AC 3 ms
6,872 KB
3_2.txt AC 3 ms
6,876 KB
evil_0.txt AC 42 ms
6,876 KB
テストケース一括ダウンロード

ソースコード

diff #
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include <stdio.h>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
//#define int long long
#define all(x) (x).begin(), (x).end()
//#define double long double

using namespace std;

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

const int MOD = 1e9 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;
template< unsigned mod >
struct RollingHash {
	vector< unsigned > hashed, power;

	inline unsigned mul(unsigned a, unsigned b) const {
		unsigned long long x = (unsigned long long) a * b;
		unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
		asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod));
		return m;
	}

	RollingHash(const string &s, unsigned base = 10007) {
		int sz = (int)s.size();
		hashed.assign(sz + 1, 0);
		power.assign(sz + 1, 0);
		power[0] = 1;
		for (int i = 0; i < sz; i++) {
			power[i + 1] = mul(power[i], base);
			hashed[i + 1] = mul(hashed[i], base) + s[i];
			if (hashed[i + 1] >= mod) hashed[i + 1] -= mod;
		}
	}

	unsigned get(int l, int r) const {
		unsigned ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
		if (ret >= mod) ret -= mod;
		return ret;
	}

	unsigned connect(unsigned h1, int h2, int h2len) const {
		unsigned ret = mul(h1, power[h2len]) + h2;
		if (ret >= mod) ret -= mod;
		return ret;
	}

	int LCP(const RollingHash< mod > &b, int l1, int r1, int l2, int r2) {
		int len = min(r1 - l1, r2 - l2);
		int low = -1, high = len + 1;
		while (high - low > 1) {
			int mid = (low + high) / 2;
			if (get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
			else high = mid;
		}
		return (low);
	}
};

using RH = RollingHash< 1000000007 >;


int H[10100];
ll dp[10010];
string S;
int N;

ll func(int i,RH &rh) {
	if (dp[i] != -1) {
		return dp[i];
	}
	ll res = 1;
	FOR(k, 1, N / 2 + 1-i) {
		int h1 = rh.get(i, i + k), h2 = rh.get(N - i -k, N - i);
		//pe(i)pe(k)pe(h1)print(h2);
		if (h1 == h2) {
			res += func(i + k,rh);
			res %= MOD;
		}
	}
	dp[i] = res;
	return res;
}


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string S; cin >> S;
	N = S.size();
	RH rh(S);
	REP(i, 10010)dp[i] = -1;

	print(func(0,rh));
}

0