結果
| 問題 | No.599 回文かい |
| ユーザー |
 はまやんはまやん
|
| 提出日時 | 2017-11-24 23:48:00 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,459 bytes |
| コンパイル時間 | 1,887 ms |
| コンパイル使用メモリ | 179,808 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-05-05 11:44:48 |
| 合計ジャッジ時間 | 2,729 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 1 ms
5,248 KB |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| evil_0.txt | WA | - |
ソースコード
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
return ModInt(u); }
bool operator==(ModInt that) const { return x == that.x; }
bool operator!=(ModInt that) const { return x != that.x; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<1000000007> mint;
#ifdef _MSC_VER
inline unsigned int __builtin_clz(unsigned int x){unsigned long r;_BitScanReverse(&r,x);return 31-r;}
inline int __lg(int __n) { return sizeof(int) * 8 - 1 - __builtin_clz(__n); }
#endif
template<class T> struct IRMQ {
int n; T *d;
IRMQ() : n(0), d(NULL) {}
template<class Iter> IRMQ(Iter begin, Iter end) : n(0), d(0) { build(begin, end); }
IRMQ(const IRMQ &y) : n(y.n), d(NULL) { if (y.n) build(y.d[0], y.d[0] + n); }
IRMQ(IRMQ &&y) : n(0), d(NULL) { swap(*this, y); }
~IRMQ() { if (n) { n = 0; delete d; d = NULL; } }
friend void swap(IRMQ &x, IRMQ &y) { swap(x.n, y.n); swap(x.d, y.d); }
IRMQ& operator=(IRMQ y) { swap(*this, y); return *this; }
template<class Iter> void build(Iter begin, Iter end) { // random access iterator
n = end - begin;
if (n == 0) return;
int g = __lg(n);
d = new T[n*(g + 1)];
rep(i, 0, n) { d[i] = *begin; ++begin; }
for (int t = 0, b = 0; t<g; t++, b += n) for (int i = 0, j = 1 << t; j <= n - (1 << t); i++, j++)
d[b + n + i] = (d[b + j] < d[b + i] ? d[b + j] : d[b + i]);
}
const T at(int i) const { return d[i]; }
const T min_v(int l, int r) const {
int g = __lg(r - l), b = n * g;
r -= 1 << g;
return d[b + r] < d[b + l] ? d[b + r] : d[b + l];
}
int min_i(int l, int r) const {
return next_less_equal(l, min_v(l, r));
}
};
class SAIS {
public:
vector<int> sa, lcp, rank;
SAIS() {}
SAIS(const string &str_) {
N = str.size() + 1;
S = vector<int>(N, 0);
for (int i = 0; i<N; i++) S[i] = str[i];
*this = SAIS(S, 256);
}
SAIS(const vector<int> &S_, int A_SIZE_, bool lcp_flag = true) : S(S_), A_SIZE(A_SIZE_) {
buildSA();
if (lcp_flag) buildLCP();
}
void init(const string &str_) {
str = str_;
N = str.size() + 1;
S = vector<int>(N, 0);
for (int i = 0; i<N; i++) S[i] = str[i];
A_SIZE = 256;
buildSA();
buildLCP();
}
private:
string str;
vector<int> S;
int A_SIZE;
int N;
vector<int> t, B;
enum { STYPE, LTYPE };
inline bool is_lms(int i) {
return i>0 && t[i] == STYPE && t[i - 1] == LTYPE;
}
void bucket() {
B = vector<int>(A_SIZE);
for (int i = 0; i<N; i++) B[S[i]]++;
for (int i = 0; i<A_SIZE - 1; i++) B[i + 1] += B[i];
}
void induced_sort() {
bucket();
for (int i = 0; i<N; i++) {
int j = sa[i] - 1;
if (j >= 0 && S[j] >= S[j + 1]) sa[B[S[j] - 1]++] = j;
}
bucket();
for (int i = N; i--; ) {
int j = sa[i] - 1;
if (j >= 0 && S[j] <= S[j + 1]) sa[--B[S[j]]] = j;
}
}
void buildSA() {
N = S.size();
sa.assign(N, -1);
if (N == 1) {
sa[0] = 0;
return;
}
t.assign(N, STYPE);
for (int i = N - 1; i--;)
if (S[i] > S[i + 1] || (S[i] == S[i + 1] && t[i + 1] == LTYPE))
t[i] = LTYPE;
bucket();
for (int i = N; i--;)
if (is_lms(i)) sa[--B[S[i]]] = i;
induced_sort();
int N1 = 0;
for (int i = 0; i<N; i++) if (is_lms(sa[i])) sa[N1++] = sa[i];
fill(sa.begin() + N1, sa.end(), -1);
int name = 0, prev = -1;
for (int i = 0; i<N1; i++) {
int cur = sa[i];
bool diff = (prev == -1);
for (int j = 0; !diff; j++) {
if (j>0 && is_lms(cur + j)) break;
if (S[cur + j] != S[prev + j]) diff = true;
}
if (diff) name++;
sa[N1 + cur / 2] = name - 1;
prev = cur;
}
vector<int> S1, sa1(N1);
for (int i = N1; i<N; i++) if (sa[i] >= 0) S1.push_back(sa[i]);
if (name == N1) for (int i = 0; i<N1; i++) sa1[S1[i]] = i;
else sa1 = SAIS(S1, name, false).sa;
N1 = 0;
for (int i = 0; i<N; i++) if (is_lms(i)) S1[N1++] = i;
for (int i = 0; i<N1; i++) sa1[i] = S1[sa1[i]];
fill(sa.begin(), sa.end(), -1);
bucket();
for (int i = N1; i--;) {
int j = sa1[i];
sa[--B[S[j]]] = j;
}
induced_sort();
}
void buildLCP() {
rank.resize(N);
lcp.resize(N - 1);
for (int i = 0; i<N; i++) rank[sa[i]] = i;
int h = 0;
for (int i = 0; i<N - 1; i++) {
int j = sa[rank[i] - 1];
if (h>0) h--;
for (; j + h<N && i + h<N && S[j + h] == S[i + h]; h++);
lcp[rank[i] - 1] = h;
}
}
public:
IRMQ<int> rmq;
void buildRMQ() {
rmq = IRMQ<int>(lcp.begin(), lcp.end());
}
int common_prefix(int x, int y) {
if (x == y) return N - 1 - x;
if (y >= N - 1) return 0;
if (rank[x] > rank[y]) swap(x, y);
return rmq.min_v(rank[x], rank[y]);
}
int compare(int x, int xn, int y, int yn) {
int l = common_prefix(x, y);
if (l >= xn || l >= yn) return xn < yn ? -1 : xn == yn ? 0 : 1;
return rank[x] < rank[y] ? -1 : x == y ? 0 : 1;
}
};
/*---------------------------------------------------------------------------------------------------
∧＿∧
∧＿∧ （´<_｀ ） Welcome to My Coding Space!
（ ´_ゝ`） / ⌒i
／ ＼ | |
/ /￣￣￣￣/ |
＿_(__ﾆつ/ ＿/ .| .|＿＿＿＿
＼/＿＿＿＿/ （u ⊃
---------------------------------------------------------------------------------------------------*/
string S;
int N;
SAIS sais;
//---------------------------------------------------------------------------------------------------
mint memo[10101];
int vis[10101];
mint f(int L, int R) {
if (vis[L]) return memo[L];
mint res = 1;
int l = L + 1, r = R - 1, n = 1;
while (l <= r) {
if (n <= sais.common_prefix(L, r + 1)) res += f(l, r);
l++;
r--;
n++;
}
vis[L] = 1;
return memo[L] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> S;
N = S.length();
sais.init(S);
sais.buildRMQ();
cout << f(0, N - 1) << endl;
}