[NK] question de calcul de 51 g pour le match lunaire Bullock

Préface

$tag:$StringUne chaîne de palindromeshashDeux pointsDifficile.
Porte de transfert :

Titre :

Vous avez une longueur de$n$La chaîne de,Vous pouvez choisir de supprimer un suffixe（Peut être vide）,Puis modifiez un des caractères de la chaîne restante,Pour en faire une chaîne de palindromes.Combien de chaînes de palindromes possibles peuvent être générées à la fin.
Il faut s'assurer que les jeux de caractères ne contiennent que des lettres minuscules tout au long du processus.Où l'opération de modification doit être modifiée,Mais les caractères peuvent être changés en caractères originaux.

Idées :
Nous pouvons diviser les chaînes restantes en trois catégories
C'est un palindrome,Il manque deux palindromes,Beaucoup de palindromes

Pour ceux qui sont eux - mêmes des palindromes
Si c'est une longueur impaire qui contribue$+26$,Sinon, contribuer$+1$

Pour un palindrome
Parce qu'il ne doit pas y avoir de non - palindrome entre les nombres impairs,Donc impair==Cas pair.Écrivez quelques contributions pour savoir$+2$

Ce qui suit est de déterminer si un palindrome

Apparemment, on peut d'abord calculer Tableau de hachage
Quand le positif et le négatif HashiL'égalité est un palindrome

Comment juger un palindrome

On peut passer par ici. Deux points

Prenez le point médian comme point de départ,Et ensuite, la moitié de la longueur

Quand $mid-len,mid+len$Il est temps que,Apparemment non.,Continuez sur les deux points

Donc monotone

Super dur à écrire.
code :

// Problem: Question de calcul
// 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 ;
}