列表

详情


NC253950. 小红的回文串

描述

小红拿到了一个字符串,字符串仅由小写字母和'?'字符组成。
小红会将每个'?'替换成任意小写字母。她希望最终字符串变成回文串。
小红想知道,有多少种不同的方案?答案请对10^9+7取模。

输入描述

一个字符串,仅由小写字母和'?'字符组成。
字符串长度不超过200000。

输出描述

合法的方案数对10^9+7取模的值。

示例1

输入:

a?a

输出:

26

说明:

aaa、aba、aca、……、aza,共有以上26种字符串是合法的。

示例2

输入:

aa?

输出:

1

说明:

只有aaa是合法的。

示例3

输入:

a?b

输出:

0

原站题解

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

C++(clang++ 11.0.1) 解法, 执行用时: 8ms, 内存消耗: 788K, 提交时间: 2023-07-17 16:08:28

#include<bits/stdc++.h>
using namespace std;
long long ans=1,mod=1e9+7;
string s;
int main()
{
	cin>>s;
	for(int i=0,j=s.size()-1;i<=j;i++,j--)
		if(s[i]=='?'&&s[j]=='?') ans=ans*26%mod;
		else if(islower(s[i])&&islower(s[j])) ans*=!(s[i]-s[j]);
	cout<<ans;
}

Python3 解法, 执行用时: 1461ms, 内存消耗: 5288K, 提交时间: 2023-07-29 19:23:36

s=input()
l,r=0,len(s)-1
a=1
while l<=r:
    c=(s[l]+s[r]).count('?')
    if s[l]!=s[r] and c==0:
        a=0
        break
    if c==2:
        a*=26
    l+=1
    r-=1
print(a%1000000007)

pypy3 解法, 执行用时: 1021ms, 内存消耗: 28552K, 提交时间: 2023-07-13 17:37:51

s=input()
l=0
r=len(s)-1
c=1
while l<=r:
    t=(s[l]+s[r]).count('?')
    if s[l]!=s[r] and t==0:
        c=0
        break
    if t==2: c*=26
    l+=1
    r-=1
print(c%(1000000007))

上一题