結果
| 問題 | No.465 PPPPPPPPPPPPPPPPAPPPPPPPP |
| ユーザー |
 nola_suz
|
| 提出日時 | 2016-12-16 19:56:38 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 15,774 bytes |
| コンパイル時間 | 1,522 ms |
| コンパイル使用メモリ | 123,404 KB |
| 実行使用メモリ | 69,880 KB |
| 最終ジャッジ日時 | 2024-05-07 16:14:09 |
| 合計ジャッジ時間 | 7,738 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
20,648 KB |
| testcase_01 | AC | 4 ms
15,756 KB |
| testcase_02 | AC | 5 ms
19,848 KB |
| testcase_03 | AC | 4 ms
15,724 KB |
| testcase_04 | AC | 3 ms
15,752 KB |
| testcase_05 | AC | 64 ms
22,192 KB |
| testcase_06 | AC | 395 ms
59,112 KB |
| testcase_07 | AC | 72 ms
26,716 KB |
| testcase_08 | AC | 373 ms
57,340 KB |
| testcase_09 | AC | 267 ms
64,992 KB |
| testcase_10 | AC | 251 ms
66,500 KB |
| testcase_11 | AC | 323 ms
64,288 KB |
| testcase_12 | AC | 217 ms
58,060 KB |
| testcase_13 | AC | 178 ms
28,152 KB |
| testcase_14 | AC | 344 ms
59,608 KB |
| testcase_15 | TLE | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| 32_ratsliveonnoevilstar.txt | -- | - |
ソースコード
#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;
}
}
// find the suffix array SA of s[0..n-1] in {1..K}^n
// require s[n-1]=0 (the sentinel!), n>=2
// use a working space (excluding s and SA) of at most 2.25n+O(1) for a constant alphabet
void SA_IS(unsigned char *s, int *SA, int n, int K, int cs) {
// cout<<"SA_IS "<<n<<" "<<K<<" "<<0<<endl;
int i, j;
// unsigned int *t = (unsigned int *) malloc(n / 8 + 1); // LS-type array in bits
unsigned int *t = new unsigned int[n / 8 + 1]; // LS-type array in bits
assert(t!=NULL);
// Classify the type of each character
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);
// stage 1: reduce the problem by at least 1/2
// sort all the S-substrings
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);
// compact all the sorted substrings into the first n1 items of SA
// 2*n1 must be not larger than n (proveable)
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;
}
// stage 3: induce the result for the original problem
// put all left-most S characters into their buckets
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:
// constructor
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;
}
};
vector<ll> calc_lcp(vector<int> sa, string s)
{
int n=s.size(),k=0;
vector<ll> lcp(n,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;
}
return lcp;
}
// vector<ll> calc_lcp(const vector<int> &sa, const string &s){
// int n = s.size();
// vector<ll> lcp(n);
// vector<int> rank(n,0);
// for (int i = 1; i < n; i++){
// rank[sa[i-1]] = i;
// }
// for(int i = 0, h = 0; i < n; i++) {
// if(rank[i] < n - 1) {
// for (int j = sa[rank[i]]; s[i + h] == s[j + h]; ++h);
// lcp[rank[i]] = h;
// if (h > 0){
// --h;
// }
// }
// }
// lcp[n - 1]=0;
// for (int i = 0; i < n; i++){
// if(s[sa[n-1] + i] != s[sa[n-2] + i]) break;
// lcp[n - 1]++;
// }
// return lcp;
// }
// RMQ pre(O(n)) query O(1)
template<class T>
class RMQ {
public:
vector<T> data;
vector<vector<int> > block;
vector<int> sblock;
int N;
// int lg;
// if Range_MAximam_Query -> return data[b] > data[a] ? b : a
int argMin(int a, int b) {
return data[b] < data[a] ? b : a;
}
// x の下位 y bit を 0 にする
int maskBits(int x, int y) {
return (x >> y) << y;
}
RMQ(){}
void init(vector<T> &v) {
data = v;
N = data.size();
// lg = 32 - __builtin_clz(N);
int blockSize = ((N - 1) >> 5) + 1;
block.assign(blockSize, vector<int>(32, 0));
for(int i = 0; i < N; i++) {
if(i % 32 == 0) block[i >> 5][0] = i;
block[i >> 5][0] = argMin(block[i >> 5][0], i);
}
for(int j = 1; j < block[0].size(); j++) {
for(int i = 0; i < block.size(); i++) {
block[i][j] = argMin(block[i][j - 1], block[min(i + (1 << (j - 1)), (int)block.size() - 1)][j - 1]);
}
}
sblock.assign(N, 0);
vector<int> st(32);
int stackSize = 0;
for(int i = 0; i < N; i++) {
if(i % 32 == 0) stackSize = 0;
while(stackSize && i == argMin(i, st[stackSize - 1])) --stackSize;
if(stackSize) {
int g = st[stackSize - 1];
sblock[i] = sblock[g] | (1 << (g % 32));
}
st[stackSize++] = i;
}
}
// min{data[i] : i in [l .. r]}
T query(int l, int r) {
if(l == r) return data[l];
int l1 = (l >> 5) + 1;
int r1 = (r >> 5) - 1;
int ret = l;
if(l1 <= r1) { // calc sparse table
int d = r1 - l1 + 1;
if(d <= 2) {
ret = argMin(ret, argMin(block[l1][0], block[r1][0]));
}
else {
int lg2 = 32 - __builtin_clz(d) - 1;
ret = argMin(ret, argMin(block[l1][lg2], block[r1 - (1 << lg2) + 1][lg2]));
}
}
if(l1 - r1 == 2) { // same block
int t = maskBits(sblock[r], l % 32);
if(t == 0) {
ret = argMin(ret, r);
}
else {
ret = argMin(ret, __builtin_ctz(t) + ((l1 - 1) << 5));
}
}
else { // other block
int t1 = maskBits(sblock[(l1 << 5) - 1], l % 32);
if(t1 == 0) {
ret = argMin(ret, (l1 << 5) - 1);
}
else {
ret = argMin(ret, __builtin_ctz(t1) + ((l1 - 1) << 5));
}
int t2 = sblock[r];
if(t2 == 0) {
ret = argMin(ret, r);
}
else {
ret = argMin(ret, __builtin_ctz(t2) + ((r1 + 1) << 5));
}
}
return data[ret];
}
};
// RollingHash<ll> rh;
string s;
int n;
RMQ<ll> rmq;
vint Rank;
int LCE(int l, int 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;
vll lcp;
void mainmain(){
cin>>s;
n = s.size();
string r = s;
reverse(ALL(r));
string sr = s+'$'+r;
sa = csa.buildCharSA(sr, 256);
lcp = 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.init(lcp);
// 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});
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();
}