DDOSvoid's Blog

CF 1679E Typical Party in Dorm

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目描述

https://codeforces.com/contest/1679/problem/E

简要题意：给定一个长度为 $n$ 的串 $S$，保证 $S$ 的字符集为 $\sum=\lbrace a,b,c,\cdots,p,q\rbrace$，$S$ 中有若干个位置的值已经确定，还有一些位置可以随便填，现在有 $m$ 次询问，每次询问给出 $\sum$ 的一个子集 $\sum’$，求将 $S$ 中未确定的位置用 $\sum’$ 中的字符来填充后有多少个子串为回文串，即求所有填法的回文子串的和

$n\le 1000,m\le 2\times 10^5$

Solution

首先我们考虑一次询问，即固定字符集为 $\sum$，回文串我们考虑用类似区间 $dp$ 的方式 $f_{i,j}$ 由 $f_{i+1,j-1}$ 转移来

我们发现转移是有规律的，即如果 $s_i$ 和 $s_j$ 都已经填充，那么如果不相等，则该区间不合法，否则 $f_{i,j}$ 就等于 $f_{i+1,j-1}$；如果有一个没填充，那么这个位置必须填对应的字符，我们记这样的对应位置的字符的集合为 $\sum’$，此时 $f_{i,j}$ 仍然等于 $f_{i+1,j-1}$；只有当 $s_i$ 和 $s_j$ 都没有填充的时候，$f_{i,j}=|\sum|f_{i+1,j-1}$

注意到只有 $\sum’\subseteq \sum$ 的时候才用贡献，但是我们不能直接统计 $f_{i,j}$ 的贡献，因为在 $[i,j]$ 外可能还有需要填充的位置，$f_{i,j}$ 需要乘上 $|\sum|$ 的若干次方，即外面的填充方案数

我们考虑从另一个角度计算贡献，我们认为总共的方案数为 $|\sum|^k$，$k$ 为整个串的未填充的位置个数，对于 $s_i$ 和 $s_j$ 一个填充另一个未填充以及 $s_i$ 和 $s_j$ 都未填充的方案，我们认为是亏损了一个未填充的位置，我们记 $f_{i,j}$ 为区间 $[i,j]$ 保留了多少未填充的位置，那么对于给定的字符集 $\sum$，当 $\sum’\subseteq \sum$ 时，$f_{i,j}$ 贡献等于 $|\sum|^{f_{i,j}}$

我们令 $f_{S,i}$ 为 $\sum’$，仍保留 $i$ 个未填充位置的方案数

那么对于询问 $ans_{S}$，我们有 $ans_{S}=\sum_{T\subseteq S}\sum_{i=0}^n|S|^{f_{T,i}}$，我们发现这个形式类似于高维前缀和，注意到 $f_{S,i}$ 在指数位置上，同时底数为 $|S|$

那么我们考虑高维前缀和比较经典的 $trick$，即我们每次只计算部分 $ans_S$，我们考虑固定 $i$，每次高维前缀和我们只计算 $popcount(S)=i$ 的 $ans_S$，那么我们令 $g_{S}=\sum_{j=0}^ni^{f_{S,j}}$，然后对 $g$ 做高维前缀和即可

时间复杂度为 $O(n^2+17(n^2+2^{17}))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstring>
#define ll long long
#define maxn 1010
#define lowbit(i) ((i) & (-i))
using namespace std;

const int p = 998244353;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

int n, m, cnt;
char s[maxn];

pair<int, int> a[maxn][maxn];

ll ppow[18][maxn];

int f[1 << 17], ans[1 << 17];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> s + 1 >> m;
    for (int i = 1; i <= n; ++i) {
        a[i][i] = make_pair(0, 0);
        cnt += s[i] == '?';
    }
    for (int len = 2; len <= n; ++len)
        for (int i = 1, j = len; j <= n; ++i, ++j) {
            a[i][j] = a[i + 1][j - 1];
            if (a[i][j].first == -1) continue;
            if (s[i] == '?' && s[j] == '?') ++a[i][j].second;
            else if (s[i] == '?') a[i][j].first |= 1 << s[j] - 'a', ++a[i][j].second;
            else if (s[j] == '?') a[i][j].first |= 1 << s[i] - 'a', ++a[i][j].second;
            else if (s[i] != s[j]) a[i][j] = make_pair(-1, -1);
        }
    
    int N = 17, M = (1 << N) - 1;
    for (int i = 0; i <= n; ++i) ppow[0][i] = 1; 
    for (int o = 1; o <= N; ++o) {
        ppow[o][0] = 1;
        for (int i = 1; i <= n; ++i) ppow[o][i] = ppow[o][i - 1] * o % p;
    }
    for (int i = 1; i <= N; ++i) {
        for (int S = 0; S <= M; ++S) f[S] = 0; 
        for (int l = 1; l <= n; ++l)
            for (int r = l; r <= n; ++r)
                if (a[l][r].first != -1)
                    f[a[l][r].first] = add(f[a[l][r].first], ppow[i][cnt - a[l][r].second]);
        for (int o = 0; o < N; ++o)
            for (int S = 0; S <= M; ++S)
                if (S >> o & 1) f[S] = add(f[S], f[S ^ 1 << o]);
        for (int S = 0; S <= M; ++S)
            if (__builtin_popcount(S) == i) ans[S] = add(ans[S], f[S]); 
    }
    for (int i = 1; i <= m; ++i) {
        char s[30]; int len, S = 0; cin >> s; len = strlen(s);
        for (int j = 0; j < len; ++j) S |= 1 << s[j] - 'a';
        cout << ans[S] << "\n";
    }
    return 0;
}