CF1679E Typical Party in Dorm 做题记录

给定一个长度为 n(1n1000)n(1\le n\le 1000) ,仅由前 1717 个英文小写字母和问号组成的字符串 ss

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

答案对 998144353998144353 取模。

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

dpi,jdp_{i,j} 表示字符集为 iiii 的二进制位表示对应字符有/没有),字符集大小为 jj 的答案,allall 为整个字符串中 ? 的个数。

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

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

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

处理完所有子串之后,需要让 dpidp_i 统计上所有 jij\in idpjdp_j,那么仿照 CF449D Jzzhu and Numbers 的思路,转移的时候先按位枚举,再枚举那一位为 11ii 来转移 dpidp_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;
	}
}