結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー nola_suznola_suz
提出日時 2016-12-16 20:22:27
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 16,175 bytes
コンパイル時間 1,530 ms
コンパイル使用メモリ 117,512 KB
実行使用メモリ 61,144 KB
最終ジャッジ日時 2024-05-07 16:15:50
合計ジャッジ時間 8,181 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
22,940 KB
testcase_01 AC 5 ms
17,796 KB
testcase_02 AC 5 ms
21,888 KB
testcase_03 AC 5 ms
17,788 KB
testcase_04 AC 5 ms
17,796 KB
testcase_05 AC 67 ms
20,672 KB
testcase_06 AC 455 ms
49,572 KB
testcase_07 AC 73 ms
27,076 KB
testcase_08 AC 447 ms
46,696 KB
testcase_09 AC 279 ms
58,488 KB
testcase_10 AC 253 ms
57,792 KB
testcase_11 AC 395 ms
54,168 KB
testcase_12 AC 241 ms
42,860 KB
testcase_13 AC 179 ms
35,912 KB
testcase_14 AC 388 ms
49,024 KB
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
32_ratsliveonnoevilstar.txt -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
		if(a[l])se.PB({{l,i}, a[l]});
	}
	se.PB({{n,INF}, INF});
	// assert(se.size()<30000);
	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();
}
0