Typical Party in Dorm
题面描述
给定一个长度为 \(n(n\le 1000)\) ，仅由前 \(17\) 个英文小写字母和问号组成的字符串 \(s\)。多次询问，每次给出一个由前 \(17\) 个英文小写字母组成的字符集 \(A\) ，你可以将 \(s\) 中的问号任意替换成 \(A\) 中的字母，求你能得到多少个不同的回文子串（两个子串不同，当且仅当起始位置，长度，两个子串的内容至少一个不同）。
Solution
注意到字符集大小 \(|\Sigma|\) 是 \(17\)，很特殊，因此考虑预处理一个字符集所有的答案。
暴力枚举串的回文中心，这里仅讨论长度为奇数的情况，偶数同理。
不难发现，当确定了一个区间过后，字符集中需要含有的字符状态是确定的，所以只需要关心不在这个区间内的问号会对答案产生什么贡献。
设总共的问号个数为 \(\operatorname{tot}\)，当前的区间内的确定的问号个数为 \(\operatorname{cnt}\)，当前区间确定必须加入字符集的元素为 \(S\)，那么考虑扩展左右边界：
- 两侧均不为问号，且两个字符不同。此时直接退出即可。
- 两侧均为问号，此时只需要确定一个问号另一个问号也随之确定，因此只需要 \(\operatorname{cnt}\) 加 \(1\)。
- 一侧为问号，一侧为字符，此时问号确定，将 \(\operatorname{cnt}\) 加 \(1\)，并将这个字符加入到 \(S\) 中。
考虑如何统计贡献。显然确定的问号不会对答案产生贡献，而未确定的问号每个都会对答案产生 \(|\Sigma|\) 的贡献。发现最后答案与 \(|\Sigma|\) 相关，因此设 \(f(S,i)\) 表示当前确定的字符集为 \(S\)，最后的字符集大小为 \(i\)。那么每次扩展边界都会对 \(f(S,k\in[1,|\Sigma|])\) 带来 \(k^{\operatorname{tot}-\operatorname{cnt}}\) 的贡献。
注意到 \(f(S,k)\) 会对所有 \(S\subseteq T\) 的 \(f(T,k)\) 产生贡献，因此最后对每个 \(f(S,k)\) 做一个子集卷积即可。
时间复杂度 \(\mathcal O(n^2|\Sigma|+|\Sigma|^22^{|\Sigma|})\)。
Code
int N;
char str[_N];
mint f[_M][20];
void init() {
int tot = 0;
For(i, 1, N) tot += str[i] == '?';
For(i, 1, N) {
auto solve = [&tot](int l, int r) -> void {
int cnt = tot, sta = 0;
while (l >= 1 && r <= N) {
if (str[l] != '?' && str[r] != '?' && str[l] != str[r]) break;
if (str[l] != '?' && str[r] == '?') sta |= 1 << (str[l] - 'a');
if (str[l] == '?' && str[r] != '?') sta |= 1 << (str[r] - 'a');
if (l != r && (str[l] == '?' || str[r] == '?')) --cnt;
For(j, 1, 17) f[sta][j] += mint(j).pow(cnt);
--l, ++r;
}
};
solve(i, i), solve(i, i + 1);
}
int lim = 1 << 17;
For(t, 1, 17) {
for (int i = 1; i < lim; i <<= 1)
for (int j = 0; j < lim; j += i << 1)
For(k, 0, i - 1) f[j+k+i][t] += f[j+k][t];
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
For(i, 1, N) cin >> str[i];
init();
int Q; cin >> Q;
while (Q--) {
string s; cin >> s;
int sta = 0;
for (char c: s) sta |= 1 << (c - 'a');
cout << f[sta][s.length()] << '\n';
}
}