[nk] Niuke monthly race 51g calculation problem

Preface

$tag:$ character string Palindrome string hash Two points difficult
Portal :

The question :

You have a length of $n$ String , You can choose to delete a suffix （ Can be null ）, Then modify one character in the remaining string , Make it a palindrome string . How many possible palindromes can be generated in the end .
It is necessary to ensure that the character set in the whole process only contains lowercase letters . The modification operation must be modified , However, the character can be modified to the original character .

Ideas :
We can divide the remaining strings into three categories
Itself is palindrome , Two palindromes are missing , A lot of palindromes are missing

For those who are palindromes
If it is an odd length, then the contribution $+26$, Otherwise, contribute $+1$

For those who are one palindrome away
Because there must be no non palindrome in the middle of odd numbers , So odd numbers == Even numbers . Write down a few knowable contributions $+2$

The following is to judge whether to reply

Obviously we can calculate Hash array
When positive and negative Hash When they are equal, they are palindromes

So how to judge the difference between a palindrome

We can go through Two points

Take the middle point as the starting point , And then half the length

When $mid-len,mid+len$ When the hash values of are equal , Obviously not , Keep bisection

Therefore, it has monotonicity

Super hard to write
code :

// Problem:  Calculation questions 
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11228/G
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false);
#define CIT cin.tie(0);
#define COT cout.tie(0);

#define ll long long
#define ull long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)
#define cer(a) cerr<<#a<<'='<<(a)<<" @ line "<<__LINE__<<" "<<endl
typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 2e5+10,INF = 0x3f3f3f3f , P = 13;

const double eps = 1e-5;

ull h[N],p[N],rh[N];

char str[N];
int n;
ull get(int l,int r){
    
	return h[r] - h[l-1]*p[r-l+1];
}
ull rget(int l,int r){
    
	return rh[r] - rh[l-1]*p[l-1];
}
void calc(){
    
	p[0] = 1;
	for(int i=1;i<=n;i++){
    
		h[i] = h[i-1]*P + str[i];
		rh[n-i+1] = rh[n-i+2]*P+str[n-i+1];
		p[i] = p[i-1]*P;
	}
}

int search(int st1,int st2,int len){
    
	int l = 1 ,r = len;
	int ans = 0 ;
	
	while(l<=r){
    
		int mid = (l+r)>>1;
		// if(get(st1+1,st1+mid) == rget(st2+1,st2 - mid)) l = mid+1;
		// else ans = mid, r = mid-1;
		
		if(h[st1+mid] - h[st1]*p[mid] == rh[st2-mid] - rh[st2]*p[mid]) l = mid+1;
		else ans = mid , r = mid-1;
		
	}
	return st1+ans;
}

void solve(){
    
	cin>>n;
	cin>>(str+1);
	calc();
	
	
	ll ans = 0 ;
	int x = 0, y = 0 ;
	
	for(int i=1;i<=n;i++){
    
		// if(get(1,i) == rget(i+2,1)){
    
		if(h[i] -  h[0]*p[i] == rh[1] - rh[i+1]*p[i]){
    
			if(i&1) ans +=26;
			else ans++;
			continue;
		}
		
		x =  search(0,i+1,i);
		y =  search(x,i+1-x,i-x);
		
		if(y == search(y,i+1-y,i-y))ans+=2;
	}
	
	cout<<ans<<endl;
	
}

int main(){
    
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}