CF1679E Typical Party in Dorm 做题记录

给定一个长度为 $n(1\le n\le 1000)$ ，仅由前 $17$ 个英文小写字母和问号组成的字符串 $s$。

多次询问，每次给出一个由前 $17$ 个英文小写字母组成的字符集 $A$ ，你可以将 $s$ 中的问号任意替换成 $A$ 中的字母，求你能得到多少个不同的回文子串

答案对 $998144353$ 取模。

观察到字符集很小，所以考虑预处理出每个字符集的答案，询问的时候快速回答。

设 $dp_{i,j}$ 表示字符集为 $i$（$i$ 的二进制位表示对应字符有/没有），字符集大小为 $j$ 的答案，$all$ 为整个字符串中 ? 的个数。

这里新增一维存储字符集大小是因为转移的时候 $dp_i$ 会统计上 $j\in i$ 的 $dp_j$，而在统计答案的时候会用到字符集大小的乘方，无法化简。

不难发现，可以枚举回文中心，然后不停往两边拓展，扩展途中记录下当前子串内部的 ? 个数 $cnt$：

• 若遇到两个不为 ? 且不同的字符或者超出字符串边界，那么停止拓展；
• 若遇到一边为 ? 另一边不为 ?，那么字符集 $sta$ 加上不为 ? 的那个字符且让 $cnt\to cnt+1$；
• 若遇到两边都为 ?，那么让 $cnt\to cnt+1$；
• 初始子串为空串，每拓展一次，就把 $dp_{sta,j}$ 加上 $j^{all-cnt}$。

处理完所有子串之后，需要让 $dp_i$ 统计上所有 $j\in i$ 的 $dp_j$，那么仿照 CF449D Jzzhu and Numbers 的思路，转移的时候先按位枚举，再枚举那一位为 $1$ 的 $i$ 来转移 $dp_i$，这样就可以避免算重。

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;
	}
}