結果
| 問題 | No.465 PPPPPPPPPPPPPPPPAPPPPPPPP |
| ユーザー |
 nola_suz
|
| 提出日時 | 2016-12-16 20:15:59 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 16,164 bytes |
| コンパイル時間 | 1,696 ms |
| コンパイル使用メモリ | 117,680 KB |
| 実行使用メモリ | 62,912 KB |
| 最終ジャッジ日時 | 2024-05-07 16:14:59 |
| 合計ジャッジ時間 | 8,918 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
15,744 KB |
| testcase_01 | AC | 4 ms
17,800 KB |
| testcase_02 | AC | 5 ms
21,892 KB |
| testcase_03 | AC | 4 ms
17,916 KB |
| testcase_04 | AC | 4 ms
17,800 KB |
| testcase_05 | AC | 58 ms
20,672 KB |
| testcase_06 | AC | 355 ms
48,332 KB |
| testcase_07 | AC | 65 ms
25,048 KB |
| testcase_08 | AC | 330 ms
48,608 KB |
| testcase_09 | AC | 239 ms
56,376 KB |
| testcase_10 | AC | 243 ms
37,700 KB |
| testcase_11 | AC | 285 ms
54,344 KB |
| testcase_12 | AC | 214 ms
28,756 KB |
| testcase_13 | AC | 158 ms
41,960 KB |
| testcase_14 | AC | 327 ms
38,292 KB |
| testcase_15 | RE | - |
| testcase_16 | AC | 455 ms
62,912 KB |
| testcase_17 | AC | 440 ms
59,436 KB |
| testcase_18 | RE | - |
| testcase_19 | AC | 496 ms
60,848 KB |
| testcase_20 | AC | 284 ms
49,456 KB |
| testcase_21 | AC | 338 ms
61,776 KB |
| 32_ratsliveonnoevilstar.txt | RE | - |
ソースコード
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>
//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else
//#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define VV(T) vector<vector< T > >
template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
v.assign(a, vector<T>(b, t));
}
template <class F, class T>
void convert(const F &f, T &t){
stringstream ss;
ss << f;
ss >> t;
}
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x) cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x)
#define debug(x)
#endif
#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
class charSA{
unsigned char mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
#define tget(i) ( (t[(i)/8]&mask[(i)%8]) ? 1 : 0 )
#define tset(i, b) t[(i)/8]=(b) ? (mask[(i)%8]|t[(i)/8]) : ((~mask[(i)%8])&t[(i)/8])
#define chr(i) (cs==sizeof(int)?((unsigned int*)s)[i]:((unsigned char *)s)[i])
#define isLMS(i) (i>0 && tget(i) && !tget(i-1))
// find the start or end of each bucket
void getBuckets(unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
int i, sum = 0;
for (i = 0; i <= K; i++)
bkt[i] = 0; // clear all buckets
for (i = 0; i < n; i++)
bkt[chr(i)]++; // compute the size of each bucket
for (i = 0; i <= K; i++) {
sum += bkt[i];
bkt[i] = end ? sum : sum - bkt[i];
}
}
// compute SAl
void induceSAl(unsigned int *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
int i, j;
getBuckets(s, bkt, n, K, cs, end); // find starts of buckets
for (i = 0; i < n; i++) {
j = SA[i] - 1;
if (j >= 0 && !tget(j))
SA[bkt[chr(j)]++] = j;
}
}
// compute SAs
void induceSAs(unsigned int *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) {
int i, j;
getBuckets(s, bkt, n, K, cs, end); // find ends of buckets
for (i = n - 1; i >= 0; i--) {
j = SA[i] - 1;
if (j >= 0 && tget(j))
SA[--bkt[chr(j)]] = j;
}
}
void SA_IS(unsigned char *s, int *SA, int n, int K, int cs) {
int i, j;
unsigned int *t = new unsigned int[n / 8 + 1]; // LS-type array in bits
assert(t!=NULL);
tset(n-2, 0);
tset(n-1, 1); // the sentinel must be in s1, important!!!
for (i = n - 3; i >= 0; i--)
tset(i, (chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1)==1))?1:0);
int *bkt = new int[K+1]; // bucket array
getBuckets(s, bkt, n, K, cs, true); // find ends of buckets
for (i = 0; i < n; i++)
SA[i] = -1;
for (i = 1; i < n; i++){
if (isLMS(i)){
SA[--bkt[chr(i)]] = i;
}
}
induceSAl(t, SA, s, bkt, n, K, cs, false);
induceSAs(t, SA, s, bkt, n, K, cs, true);
int n1 = 0;
for (i = 0; i < n; i++)
if (isLMS(SA[i]))
SA[n1++] = SA[i];
// find the lexicographic names of all substrings
for (i = n1; i < n; i++)
SA[i] = -1; // init the name array buffer
int name = 0, prev = -1;
for (i = 0; i < n1; i++) {
int pos = SA[i];
bool diff = false;
for (int d = 0; d < n; d++)
if (prev == -1 || chr(pos+d) != chr(prev+d) || tget(pos+d) != tget(prev+d)) {
diff = true;
break;
} else if (d > 0 && (isLMS(pos+d) || isLMS(prev+d)))
break;
if (diff) {
name++;
prev = pos;
}
pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
SA[n1 + pos] = name - 1;
}
for (i = n - 1, j = n - 1; i >= n1; i--)
if (SA[i] >= 0)
SA[j--] = SA[i];
// stage 2: solve the reduced problem
// recurse if names are not yet unique
int *SA1 = SA, *s1 = SA + n - n1;
if (name < n1){
SA_IS((unsigned char*) s1, SA1, n1, name - 1, sizeof(int));
}
else{
// generate the suffix array of s1 directly
for (i = 0; i < n1; i++)
assert(s1[i]>=0),SA1[s1[i]] = i;
}
getBuckets(s, bkt, n, K, cs, true); // find ends of buckets
for (i = 1, j = 0; i < n; i++)
if (isLMS(i))
s1[j++] = i; // get p1
for (i = 0; i < n1; i++)
SA1[i] = s1[SA1[i]]; // get index in s
for (i = n1; i < n; i++)
SA[i] = -1; // init SA[n1..n-1]
for (i = n1 - 1; i >= 0; i--) {
j = SA[i];
SA[i] = -1;
SA[--bkt[chr(j)]] = j;
}
induceSAl(t, SA, s, bkt, n, K, cs, false);
induceSAs(t, SA, s, bkt, n, K, cs, true);
delete[] bkt;
delete[] t;
}
public:
charSA(){
}
vector<int> buildCharSA(string &u, int K, int cs = 1){
int n = u.size();
int *sa = new int[n+1]; // integer sequence
unsigned char* s = (unsigned char *) u.c_str();
SA_IS(s, sa, n + 1, K, cs);
vector<int> ret(n);
for(int i = 0; i < n; i++){
ret[i]=sa[i+1];
}
delete[] sa;
return ret;
}
};
ll lcp[1000010];
void calc_lcp(vector<int> sa, string s)
{
int n=s.size(),k=0;
vector<int> rank(n,0);
for(int i=0; i<n; i++) rank[sa[i]]=i;
for(int i=0; i<n; i++, k?k--:0)
{
if(rank[i]==n-1) {k=0; continue;}
int j=sa[rank[i]+1];
while(i+k<n && j+k<n && s[i+k]==s[j+k]) k++;
lcp[rank[i]+1]=k;
}
}
typedef int INT;
typedef long long VAL;
/* compare the value inside the array */
#define VAL_LT(x,y) x < y
struct rmqinfo {
INT alen; // length of original array
VAL * array; // pointer to original array
INT ** sparse;
INT * block_min;
INT * labels;
};
INT rm_query_naive(VAL * a, INT x, INT y);
struct rmqinfo * rm_query_preprocess(VAL * a, INT alen);
INT rm_query(const struct rmqinfo * info, INT x, INT y);
void rm_free(struct rmqinfo * info);
/* clear the least significant x-1 bits */
static inline INT clearbits(INT n, INT x){
return((n >> x) << x);
}
static inline INT intlog2(INT n){
return(__builtin_clz(n)^31);
}
static inline INT lsbset (INT n){
return(__builtin_ctz(n));
}
struct rmqinfo * rm_query_preprocess(VAL * array, INT alen){
struct rmqinfo * info;
INT i, j, g, rows, cols, block_cnt, rowelmlen;
INT *block_min, **sparse, *labels;
INT gstack[32], gstacksize = 0;
info = new rmqinfo;
block_cnt = ((alen-1) >> 5) + 1;
block_min = new INT[block_cnt];
for(i = j = 0; i < alen; i++){
if(i % 32 == 0){
if(i > 0) j++;
block_min[j] = i;
} else if(VAL_LT(array[i],array[block_min[j]])){
block_min[j] = i;
}
}
rows = intlog2(block_cnt);
sparse = NULL;
if(rows > 0){
sparse = new INT*[rows];
sparse[0] = new INT[block_cnt - 1];
for(i = 0; i < block_cnt - 1; i++){
if(VAL_LT(array[block_min[i+1]],array[block_min[i]]))
sparse[0][i] = block_min[i+1];
else
sparse[0][i] = block_min[i];
}
for(j = 1; j < rows; j++){
rowelmlen = 2 << j; /* 2^{j+1} */
cols = block_cnt - rowelmlen + 1;
sparse[j] = new INT[cols];
for(i = 0; i < cols; i++){
if(VAL_LT(array[sparse[j-1][i + (rowelmlen >> 1)]],array[sparse[j-1][i]]))
sparse[j][i] = sparse[j-1][i + (rowelmlen >> 1)];
else
sparse[j][i] = sparse[j-1][i];
}
}
}
labels = new INT[alen];
for(i = 0; i < alen; i++){
if(i % 32 == 0) gstacksize = 0;
labels[i] = 0;
while(gstacksize > 0 && (VAL_LT(array[i],array[gstack[gstacksize-1]]))){
gstacksize--;
}
if(gstacksize > 0){
g = gstack[gstacksize-1];
labels[i] = labels[g] | (1 << (g%32));
}
gstack[gstacksize++] = i;
}
info->array = array;
info->sparse = sparse;
info->block_min = block_min;
info->labels = labels;
info->alen = alen;
return info;
}
INT rm_query(const struct rmqinfo * info, INT l, INT r){
INT blocknum_l, blocknum_r, blockdiff, blockmin;
INT tmp, v, bpos;
INT v1, v2, pos1, pos2;
if(l == r) return l;
if(l > r){
tmp = l; l = r; r = tmp;
}
blocknum_l = (l >> 5); blocknum_r = (r >> 5); /* obtain which blocks l and r will come in */
bpos = blocknum_l << 5;
switch(blockdiff = blocknum_r - blocknum_l){
case 0:
v = clearbits(info->labels[r], l % 32); /* clear (x - 1) insiginificant bits */
return ((v == 0) ? r : bpos + lsbset(v));
break;
case 1:
tmp = bpos + 31;
v1 = clearbits(info->labels[tmp], l%32);
v2 = info->labels[r];
pos1 = (v1 == 0) ? tmp : (bpos + lsbset(v1));
pos2 = (v2 == 0) ? r : lsbset(v2) + (blocknum_r<<5);
return((VAL_LT(info->array[pos2],info->array[pos1])) ? pos2 : pos1);
break;
default:
tmp = bpos + 31;
v1 = clearbits(info->labels[tmp], l%32);
v2 = info->labels[r];
pos1 = (v1 == 0) ? tmp : (bpos + lsbset(v1));
pos2 = (v2 == 0) ? r : lsbset(v2) + (blocknum_r<<5);
if(blockdiff == 2){
blockmin = info->block_min[blocknum_l+1];
} else {
int t1, t2, k;
k = intlog2(blockdiff-1) - 1;
t1 = info->sparse[k][blocknum_l+1];
t2 = info->sparse[k][blocknum_r - (1 << (k+1))];
blockmin = (VAL_LT(info->array[t2],info->array[t1])) ? t2 : t1;
}
pos1 = (VAL_LT(info->array[blockmin],info->array[pos1])) ? blockmin : pos1;
return((VAL_LT(info->array[pos2],info->array[pos1])) ? pos2 : pos1);
}
}
rmqinfo *rmq;
string s;
int n;
// RMQ<ll> rmq;
vint Rank;
int LCE(int l, int r){
return lcp[rm_query(rmq, min(Rank[l], Rank[r])+1, max(Rank[l], Rank[r]))];
// return rmq.query(min(Rank[l], Rank[r])+1, max(Rank[l], Rank[r]));
}
static const int MAX_SIZE = 1 << 22; //segment tree のサイズ。 2^17 ≒ 1.3 * 10^5
ll all[2 * MAX_SIZE - 1], part[2 * MAX_SIZE - 1]; // segment tree
//区間[a, b)に値xを加算する.
void add(int a, int b, ll x, int k = 0, int l = 0, int r = MAX_SIZE)
{
if (a <= l && r <= b){ //[l, r)が[a, b)に完全に内包されていれば
all[k] += x; //[l, r)の全ての区間が持つ値としてxを足す.
}
else if (l < b && a < r){ //[l, r)と[a, b)が交差していれば
part[k] += (min(b, r) - max(a, l)) * x; //交差している分の値を, 部分的な和を持つノードに加算する.
add(a, b, x, k * 2 + 1, l, (l + r) / 2); //子でも同じ処理を行う.
add(a, b, x, k * 2 + 2, (l + r) / 2, r); //〃.
}
}
ll sum(int a, int b, int k = 0, int l = 0, int r = MAX_SIZE)
{
if (b <= l || r <= a){ //[a, b)と[l, r)が全く交差しない場合
return (0);
}
else if (a <= l && r <= b){ //完全に内包されていれば
return (all[k] * (r - l) + part[k]);
}
else { //[l, r)と[a, b)が交差していれば
ll res;
res = (min(b, r) - max(a, l)) * all[k]; //そのノードの全ての要素が持つ値のうち, [a, b)に属すものの分だけを加算する.
res += sum(a, b, k * 2 + 1, l, (l + r) / 2); //子ノードで和を求める.
res += sum(a, b, k * 2 + 2, (l + r) / 2, r); //〃
return (res);
}
}
bool isPal(string a){
string b = a;
reverse(ALL(b));
return a == b;
}
int func(string a){
int ret = 0;
rep(i,a.size()-1){
if(isPal(a.substr(0,i+1))&&isPal(a.substr(i+1))) {
ret++;
}
}
return ret;
}
// int ff(string a){
// int n = a.size();
// rep(i,n){
// rep(j,i){
// for(int k=i+2)
// }
// }
// }
vector<pair<pii,int>> se;
charSA csa;
vint sa;
void mainmain(){
cin>>s;
n = s.size();
string r = s;
reverse(ALL(r));
string sr = s+'$'+r;
sa = csa.buildCharSA(sr, 256);
calc_lcp(sa, sr);
// rep(i,sa.size()){
// cout<<i<<" "<<lcp[i]<<" "<<sr.substr(sa[i])<<endl;
// }
Rank = vint(sr.size());
rep(i,Rank.size()){
Rank[sa[i]] = i;
}
rmq = rm_query_preprocess(lcp, 2*n+1);
// return;
// cout << LCE(0, s.size()+13) << endl;
// cout<<sr.substr(s.size()+13) << endl;
// return;
vll a(n);
a[1] = 1;
reep(i,1,n-1){
int le = i+1;
// cout<<i<<endl;
if(le&1){
int tl = le/2;
int c = i-tl;
// cout<<c+1<<" "<<2*n-(c-1) << endl;
// cout<<sr.size() << endl;
if(tl == LCE(c+1, 2*n-(c-1))) a[i+1]=1;
}
else{
int tl = le/2;
int c = i-tl;
if(tl == LCE(c+1, 2*n-c)) a[i+1]=1;
}
}
// rep(i,n){
// cout<<a[i];
// }cout<<endl;
// return;
se.PB({{-INF,-1}, -INF});
rep(i,n){
int l=i;
while(i<n&&a[l]==a[i]) i++;
i--;
// cout<<l<<" "<<i<<" "<<a[l]<<endl;
se.PB({{l,i}, a[l]});
}
se.PB({{n,INF}, INF});
assert(se.size()<10000);
rep(i,n){
// cout<<i<<endl;
if(i+1<n){
// even pal
int le = LCE(i+1, 2*n-i);
if(le>=1){
int l = i-le+1;
int r = i;
// if(i==5) cout<<l<<" "<<r<<endl;
auto it = lower_bound(ALL(se), mkp(pii(r, INF), 1));
it--;
while(1){
// cout<<"hoge"<<endl;
int ll,rr,t;
ll=it->F.F,rr=it->F.S,t=it->S;
// if(i==5) cout<<ll<<" "<<rr<<" "<<t<<endl;
if(rr<l) break;
if(t){
int tl = max(l, ll);
int tr = min(r, rr);
int tle = i-tr;
// if(i==5){
// cout<<i+tle+1<<" "<<i+tle+1+(tr-tl) << endl;
// }
add(i+tle+1, i+tle+2+(tr-tl), 1);
}
// cout<<"hoge"<<endl;
// if(it == se.begin()) break;
it--;
}
}
}
// odd pal
int le = (i==0?0:LCE(i+1, 2*n-(i-1)));
int l = i-le;
int r = i;
auto it = lower_bound(ALL(se), mkp(pii(r,INF),1));
it--;
while(1){
int ll,rr,t;
ll=it->F.F,rr=it->F.S,t=it->S;
// if(i==1) cout<<ll<<" "<<rr<<" "<<t<<endl;
if(rr<l) break;
if(t){
int tl = max(l, ll);
int tr = min(r, rr);
int tle = i-tr;
add(i+tle, i+tle+1+(tr-tl), 1);
}
// if(it == se.begin()) break;
it--;
}
}
vll b(n);
rep(i,n-1){
b[i] = sum(i,i+1);
}
// rep(i,n){
// cout<<b[i];
// }cout<<endl;
vll c(n);
c[n-1]=1;
reep(i,1,n-1){
int le = i+1;
if(le&1){
int tl = le/2;
int ce = n-1-tl;
if(tl == LCE(ce+1, 2*n-(ce-1))) c[n-1-i]=1;
}
else{
int tl = le/2;
int ce = n-1-tl;
if(tl == LCE(ce+1, 2*n-ce)) c[n-1-i]=1;
}
}
// rep(i,n){
// cout<<c[i];
// }cout<<endl;
// rep(i,n){
// if(b[i]){
// int t = func(s.substr(0,i+1));
// if(t != b[i]){
// cout<<"error "<<i<<" "<<t<<endl;
// }
// }
// }
for(int i=n-2;i>=0;i--){
c[i] += c[i+1];
}
ll ans = 0;
rep(i,n-2){
ans += b[i] * c[i+2];
}
cout << ans << endl;
// cout<<ff(s)<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout<<fixed<<setprecision(20);
mainmain();
}