计算题

NC237272. 计算题

描述

你有一个长度为 $n$ 的字符串，你可以选择删除一段后缀（可以为空），然后修改剩余串中的一个字符，使其变成回文串。请问最后能生成多少种可能的回文串。

需要保证整个过程中的字符集仅包含小写字母。其中修改操作必须修改，但可将字符修改为原字符。

输入描述

第一行输入一个数字，代表字符串的长度，。
第二行输入一行字符串。

输出描述

一个整数。

示例1

输入:

3
abc

输出:

说明:

对于删除后缀长度为 $0$ 的情况，我们只能修改第一个字符为 $c$ ，或者修改第三个字符为 $a$ ， $2$ 种字符串。
对于删除后缀长度为 $1$ 的情况，我们只能修改第一个字符为 $b$ ，或者修改第二个字符为 $a$ ， $2$ 种字符串。
对于删除后缀长度为 $2$ 的情况，我们可以将第一个字符修改为任意小写字符，一共有 $26$ 种字符串。
所以总共有 $30$ 种情况。

示例2

输入:

3
aba

输出:

说明:

对于删除后缀长度为 $0$ 的情况，我们可以修改成 $aXa$ 的方式，总共有 $26$ 种字符串
对于删除后缀长度为 $1$ 的情况，我们只能修改第一个字符为 $b$ ，或者修改第二个字符为 $a$ ， $2$ 种字符串。
对于删除后缀长度为 $2$ 的情况，我们可以将第一个字符修改为任意小写字符，一共有 $26$ 种字符串。
所以总共有 $54$ 种情况。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 177ms, 内存消耗: 24852K, 提交时间: 2022-06-04 01:26:09

#include<bits/stdc++.h>
using namespace std;

unsigned long long ha1[1000005],ha2[1000005],pw[1000005],base=1e9+7;
char R[1000005];
int cal(int st1,int st2,int len)
{
	int l=1,r=len,mid,ans=0;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(ha1[st1+mid]-ha1[st1]*pw[mid]==ha2[st2-mid]-ha2[st2]*pw[mid])l=mid+1;
		else ans=mid,r=mid-1;
	}
	return st1+ans;
}
int main()
{
	int i,n,x,y,ans=0;
	scanf("%d%s",&n,R+1);
	assert(n>=1&&n<=1e6);
	for(pw[0]=i=1;i<=n;i++)
	{
		assert(R[i]>='a'&&R[i]<='z');
		ha1[i]=ha1[i-1]*base+R[i];
		ha2[n-i+1]=ha2[n-i+2]*base+R[n-i+1];
		pw[i]=pw[i-1]*base;
	}
	for(i=1;i<=n;i++)
	{
		if(ha1[i]-ha1[0]*pw[i]==ha2[1]-ha2[i+1]*pw[i])
		{
			if(i&1)ans+=26;
			else ans++;
			continue;
		}
		x=cal(0,i+1,i);
		y=cal(x,i+1-x,i-x);
		if(y==cal(y,i+1-y,i-y))ans+=2;
	}
	printf("%d\n",ans);
    return 0;
}