给定一个长度为 ,仅由前 个英文小写字母和问号组成的字符串 。
多次询问,每次给出一个由前 个英文小写字母组成的字符集 ,你可以将 中的问号任意替换成 中的字母,求你能得到多少个不同的回文子串
答案对 取模。
观察到字符集很小,所以考虑预处理出每个字符集的答案,询问的时候快速回答。
设 表示字符集为 ( 的二进制位表示对应字符有/没有),字符集大小为 的答案, 为整个字符串中 ?
的个数。
这里新增一维存储字符集大小是因为转移的时候 会统计上 的 ,而在统计答案的时候会用到字符集大小的乘方,无法化简。
不难发现,可以枚举回文中心,然后不停往两边拓展,扩展途中记录下当前子串内部的 ?
个数 :
- 若遇到两个不为
?
且不同的字符或者超出字符串边界,那么停止拓展; - 若遇到一边为
?
另一边不为?
,那么字符集 加上不为?
的那个字符且让 ; - 若遇到两边都为
?
,那么让 ; - 初始子串为空串,每拓展一次,就把 加上 。
处理完所有子串之后,需要让 统计上所有 的 ,那么仿照 CF449D Jzzhu and Numbers 的思路,转移的时候先按位枚举,再枚举那一位为 的 来转移 ,这样就可以避免算重。
int n,q;
char s[S],str[S];
int dp[1<<17][25];
inline int qpow(int x,int y)
{
int res=1;
for(;y>0;y>>=1,x=1ll*x*x%p) res=(y&1)?1ll*res*x%p:res;
return res;
}
inline void slove()
{
cin>>n;
cin>>(s+1);
int all=0;
for(int i=1;i<=n;i++) all+=s[i]=='?';
for(int i=1;i<=n;i++)
{
int l=i+1,r=i-1;
int sta=0,cnt=0;
while(l>1&&r<n&&(s[l-1]==s[r+1]||s[l-1]=='?'||s[r+1]=='?'))
{
l--,r++;
if(s[l]=='?'&&s[r]!='?') sta|=1<<s[r]-'a';
if(s[l]!='?'&&s[r]=='?') sta|=1<<s[l]-'a';
if(l!=r&&(s[l]=='?'||s[r]=='?')) cnt++;
for(int j=1;j<=17;j++) dp[sta][j]=(dp[sta][j]+qpow(j,all-cnt))%p;
}
l=i+1,r=i;
sta=0,cnt=0;
while(l>1&&r<n&&(s[l-1]==s[r+1]||s[l-1]=='?'||s[r+1]=='?'))
{
l--,r++;
if(s[l]=='?'&&s[r]!='?') sta|=1<<s[r]-'a';
if(s[l]!='?'&&s[r]=='?') sta|=1<<s[l]-'a';
if(s[l]=='?'||s[r]=='?') cnt++;
for(int j=1;j<=17;j++) dp[sta][j]=(dp[sta][j]+qpow(j,all-cnt))%p;
}
}
for(int j=0;j<=16;j++)
for(int i=0;i<=(1<<17)-1;i++)
if((i>>j)&1)
for(int k=1;k<=17;k++) dp[i][k]=(dp[i][k]+dp[i^(1<<j)][k])%p;
cin>>q;
while(q-->0)
{
cin>>(str+1);
int len=strlen(str+1),sta=0;
for(int i=1;i<=len;i++) sta|=1<<str[i]-'a';
cin<<dp[sta][len]<<endl;
}
}