結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
コンテスト
ユーザー chaemon
提出日時 2016-12-16 23:57:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,758 bytes
コンパイル時間 1,771 ms
コンパイル使用メモリ 172,876 KB
実行使用メモリ 32,644 KB
最終ジャッジ日時 2024-11-30 21:54:10
合計ジャッジ時間 3,133 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #includes {{{
#include<bits/stdc++.h>
using namespace std;
// }}}
// pre-written code {{{
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair
#define PB push_back
#define CLEAR(c,d) memset((c),(d),sizeof(c))
#define TO_STRING(VariableName) # VariableName
#define DB(c) cout<<TO_STRING(c)<<"="<<(c)<<endl

typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;

typedef pair<int,int> pii;


struct IO{ }io;//dummy
#define endl "\n"
IO& operator>>(IO &io,int &n){scanf("%d",&n);return io;}
IO& operator>>(IO &io,unsigned int &n){scanf("%u",&n);return io;}
IO& operator>>(IO &io,long long &n){scanf("%lld",&n);return io;}
IO& operator>>(IO &io,unsigned long long &n){scanf("%llu",&n);return io;}
IO& operator>>(IO &io,double &n){scanf("%lf",&n);return io;}
IO& operator>>(IO &io,long double &n){scanf("%Lf",&n);return io;}
IO& operator>>(IO &io,char *c){scanf("%s",c);return io;}
 
IO& operator<<(IO &io,const int &n){printf("%d",n);return io;}
IO& operator<<(IO &io,const unsigned int &n){printf("%u",n);return io;}
IO& operator<<(IO &io,const long long &n){printf("%lld",n);return io;}
IO& operator<<(IO &io,const unsigned long long &n){printf("%llu",n);return io;}
IO& operator<<(IO &io,const double &n){printf("%lf",n);return io;}
IO& operator<<(IO &io,const long double &n){printf("%Lf",n);return io;}
IO& operator<<(IO &io,const char c[]){printf("%s",c);return io;}
// }}}

const int P = 137;
const int D = 500010;
uInt p[D];
uInt pp[D],tail_p_ct[D];

string S;

pair<uInt,uInt> get2(int ii,int ij){
	uInt h = 0ull,rev_h = 0ull;
	for(int i=ii;i<ij;i++){
		h+=p[i]*(uInt)S[i];
		rev_h*=P;rev_h+=(uInt)S[i];
	}
	return make_pair(h,rev_h);
}

uInt get(int ii,int ij){
	uInt h = 0ull;
	for(int i=ii;i<ij;i++){
		h+=p[i]*(uInt)S[i];
	}
	return h;
}

struct Palin{
	int r,s;
	uInt hr,hs;
	int n;//n r-s, n-1 s-s
	int tail;
	Palin(int r,uInt hr,int s,uInt hs,int n,int tail):r(r),hr(hr),hs(hs),s(s),n(n),tail(tail){}
};

vector<Palin> vp;

//{{{ main function
int main() {
	memset(pp,0,sizeof(pp));
	cin>>S;
	uInt h = 0ull, rev_h = 0ull, t = 1ull;
	for(int i=0;i<S.size();i++){
		p[i] = t;
		t*=P;
	}
	uInt ct = 0;
	for(int i=S.size()-1;i>=0;i--){
		h+=p[S.size()-1-i]*(uInt)S[i];
		rev_h*=P;rev_h+=(uInt)S[i];
		if(h==rev_h){
			ct++;
		}
		tail_p_ct[i] = ct;
	}
	h = 0ull, rev_h = 0ull;
	for(int i=0;i<S.size();){
		h+=p[i]*(uInt)S[i];
		rev_h*=P;rev_h+=(uInt)S[i];
		i++;
		if(h==rev_h){
//			cerr<<"palindrome: "<<i<<endl;
			if(i>=2){
				int d;
				d = i - vp.back().tail;
//				cerr<<"palindrome: "<<i<<" "<<d<<endl;
				int r = i%d, s = d-r;
				if(vp.size()>0){
//					cerr<<"count previous pp"<<endl;
//					cerr<<r<<" "<<s<<endl;
					uInt h = 0, rev_h = 0;
					for(int i=r;i<r+s;){
						h+=p[i-r]*(uInt)S[i];
						rev_h*=P;rev_h+=(uInt)S[i];
						i++;
						if(h==rev_h){
//							cerr<<"found: "<<r<<" "<<i<<endl;
							//find rsrsrsrs or ssssss
							int ct = 0;
							if(ct<vp.back().n)pp[i]++;
							while(1){
								if(vp.back().r!=0){
									pair<uInt,uInt> u = get2(i,i+vp.back().r);
									if(u.first!=vp.back().hr)break;
									i+=vp.back().r;
									h+=p[vp.back().r]*u.first;
									rev_h*=p[vp.back().r];
									rev_h+=u.second;
								}
								pair<uInt,uInt> u = get2(i,i+vp.back().s);
								if(u.first!=vp.back().hs)break;
								i+=vp.back().s;
								h+=p[vp.back().s]*u.first;
								rev_h*=p[vp.back().s];
								rev_h+=u.second;
								ct++;
								if(ct<vp.back().n)pp[i]++;
							}
						}
					}
				}
				uInt hr = get(0,r), hs = get(r,r+s);
				int section_ct = 0;
				//r=0: ssssssss
				//r!=0: rsrsrsrs
				int i2 = i;
				uInt h2 = h, rev_h2 = rev_h;
				while(1){
					section_ct++;
					if(r!=0){
						if(i2+r>S.size())break;
						pair<uInt,uInt> u = get2(i2,i2+r);
						if(u.first!=hr){
							break;
						}
						i2+=r;
						h2+=p[r]*u.first;
						rev_h2*=p[r];
						rev_h2+=u.second;
					}
					if(i2+s>S.size())break;
					pair<uInt,uInt> u = get2(i2,i2+s);
					if(u.first!=hs){
						break;
					}
					i2+=s;
					h2+=p[s]*u.first;
					rev_h2*=p[s];
					rev_h2+=u.second;
				}
//				cerr<<"insert: "<<i<<endl;
				vp.push_back(Palin(r,hr,s,hs,section_ct,i2));
				h = h2;
				rev_h2 = rev_h;
				i = i2;
			}else{
				vp.push_back(Palin(0,0,1,h,1,1));
			}
		}
	}
	/*
	REP(i,S.size())cout<<pp[i]<<" ";
	cout<<endl;
	REP(i,S.size())cout<<tail_p_ct[i]<<" ";
	cout<<endl;
	*/
	uInt ans = 0;
	REP(i,S.size()){
		ans+=pp[i]*tail_p_ct[i+1];
	}
	cout<<ans<<endl;
	return 0;
}
//}}}
0