DDOSvoid's Blog

CF 1620G Subsequences Galore

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

题目描述

https://codeforces.com/contest/1620/problem/G

简要题意：首先定义 $f([s_1, s_2,\cdots, s_k])$ 为本质不同的子串个数，要求这些子串至少是 $s_1,s_2,\cdots,s_k$ 中某一个串的子序列，现在给 $n$ 个串 $s_i$，求对于 $s$ 的 $2^n$ 种选择，求它们的 $f$，对于一种选择 $s_{i_1},s_{i_2,},\cdots,s_{i_k}$，求出 $f([s_{i_1},s_{i_2,},\cdots,s_{i_k}]) \bmod 998244353$，将其乘上 $k\times (i_1+i_2+\cdots+i_k)$，然后将求出的 $2^n$ 个 $f$ 异或起来，另外对于给定的串 $s_i$，保证 $s_i$ 中的字母是按照字典序排列

$n\le 23$

Solution

注意到集合的并是很难求的，我们可以求集合的交，同时我们发现集合的交很好求，就是每种字母的最少出现次数加一的乘积，我们令集合 $S$ 的交的值为 $f_S$，集合 $S$ 的并为 $g_S$，那么 $g_S=\sum_{T\subseteq S}(-1)^{|T|+1}f_T$

这里我们暴力的复杂度是 $O(3^n)$，显然是无法通过此题的，同时我们注意到这个形式有一点像高维前缀和，注意到这个系数只跟集合的大小的奇偶性有关，所以我们将集合分奇数和偶数各做一遍高为前缀和即可

时间复杂度 $O(2^n(n+26))$

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define maxn 24
#define maxm 20010
#define ll long long
#define INF 1000000000
using namespace std;

const int p = 998244353;

int n, num[maxn][26];
char s[maxm];

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

    cin >> n; int M = (1 << n) - 1, ch[26];
    for (int i = 1; i <= n; ++i) {
        cin >> s + 1; int l = strlen(s + 1); 
        for (int j = 1; j <= l; ++j) ++num[i][s[j] - 'a'];
    }
    for (int S = 1; S <= M; ++S) {
        int cnt = 0; 
        for (int i = 0; i < 26; ++i) ch[i] = INF; 
        for (int i = 1; i <= n; ++i) {
            if (!(S >> i - 1 & 1)) continue; g[S] += i; ++cnt;
            for (int c = 0; c < 26; ++c) ch[c] = min(ch[c], num[i][c]); 
        } f[S][cnt & 1] = 1; g[S] *= cnt;
        for (int i = 0; i < 26; ++i)
            if (ch[i] != INF) f[S][cnt & 1] = 1ll * f[S][cnt & 1] * (ch[i] + 1) % p;
    }
    for (int o = 0; o < n; ++o)
        for (int S = 0; S <= M; ++S)
            if (S >> o & 1) {
                f[S][0] = (f[S][0] + f[S ^ 1 << o][0]) % p;
                f[S][1] = (f[S][1] + f[S ^ 1 << o][1]) % p;
            }
    ll ans = 0; 
    for (int S = 1; S <= M; ++S) ans ^= 1ll * g[S] * ((p + f[S][1] - f[S][0]) % p);
    cout << ans << "\n";
    return 0; 
}