题目 | We Love Strings

2023牛客暑期多校训练营7

I - We Love Strings

https://ac.nowcoder.com/acm/contest/57361/I

题意

给定 $n$ 个仅含 0,1,? 的正则串，? 可以匹配一个 0 或 1，问有多少个 $01$ 串可以被至少一个正则串匹配。$1\le n\le 400$，$\sum |s_i|\le 400$.

题解

这道题的突破口不在题目本身，而在数据范围上。正则串个数最多 $400$ 个，同时包含的总字符数最多 $400$ 个，这代表正则串多的时候，每个正则串的长度短；正则串长的时候，正则串数量少。（不过要注意的是同一个输入内，正则串不一定一样长）所以，可以使用两种不同的解法，取长补短过掉这题。

暴力法

如果 0/1 串长度为 $k$，那么对于 $\stackrel{k\mathrm{个}}{\overbrace{0\dots 0000}}\sim \stackrel{k\mathrm{个}}{\overbrace{1\dots 1111}}$ 的每个 0/1 串，逐一考察判断是否存在正则串 $s_i$ 与它匹配，若匹配则答案 $+1$.

暴力法时间复杂度为 $O(nk\cdot 2^k)$. 当 $k$ 较小时可以接受，例如 $k=20$ 时数量级为 $4\cdot {10}^8$.

容斥原理法

对于一个正则串 $s_i$，记能与它匹配的 0/1 串的集合为 $A_i$，那么根据容斥原理：

$${\displaystyle \begin{array}{rl}\left|\bigcup _{i=1}^n{A}_i\right|=& \sum _{i=1}^n|A_i|-\sum _{1\le i<j\le n}|A_i\cap A_j|+\sum _{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots +(-1{)}^{n-1}|A_1\cap \cdots \cap A_n|.\end{array}}$$

接下来的要解决的问题就是怎么统计每种交情况的集合数量了。

对于 $n$ 个正则串的集合 $S$，我们取一个子集 $T\subseteq S$，可以计算出能同时匹配 $T$ 中所有正则串的 0/1 串个数。计算方法为：

1. 初始化一个串 $M$ 为 $\stackrel{k\mathrm{个}}{\overbrace{?\dots ????}}$

2. 对于每个 $s_i\in T$，逐位考察：

   1. 如果 $s_{i,j}=0/1$，$M_j=?$：令 $M_j=s_{i,j}$.
   2. 如果 $s_{i,j}=?$，$M_j=0/1$：不操作
   3. 如果 $s_{i,j}=0/1$，$M_j=1/0$：发生矛盾！直接退出算法，匹配数为 $0$.
3. 统计串 $M$ 内的 $?$ 数目为 $t$
4. 能同时匹配 $T$ 中所有正则串的 0/1 串数目为：$2^t$

最后，对于元素个数为奇数的子集，加上它们的答案，对于元素个数为偶数的子集，减去它们的答案，便是最终答案了。

容斥原理法时间复杂度为 $O(nk\cdot 2^n)$. 当 $n$ 较小时可以接受，例如 $n=20$ 时数量级为 $4\cdot {10}^8$.

两种方法结合

可以发现暴力法时间复杂度关于 $k$ 呈指数上升，容斥原理法关于 $n$ 呈指数上升，那么取长补短：

• 当 $k\le 20$ 时，数据范围保证 $n\ge 20$，选择暴力法.
• 当 $k>20$ 时，数据范围保证 $n<20$，选择容斥原理法.

（时间复杂度算出来 $4\cdot {10}^8$ 级别看着很大，但是该题时间给到了 3s，并且实际跑出来耗时在 200ms 内，还是很充裕的）

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

constexpr int MOD = 998244353;

// 暴力 Brute Force
int brute_force(vector<string> &arr)
{
    int len = arr.front().length();
    int siz = arr.size();
    int res = 0;
    for (int i = 0; i < (1 << len); i++)
    {
        for (int j = 0; j < siz; j++)
        {
            bool flag = true;
            for (int k = 0; k < len; k++)
            {
                if (arr[j][k] == '?')
                    continue;
                if (arr[j][k] != (i >> k & 1) + '0')
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                res++;
                break;
            }
        }
    }
    return res;
}

// 容斥原理 Include-Exclude Principle
int inc_exc(vector<string> &arr)
{
    int len = arr.front().length();
    int siz = arr.size();
    int res = 0;
    for (int i = 1; i < (1 << siz); i++)
    {
        bool flag = true;
        string match(len, '?');
        for (int j = 0; flag && j < siz; j++)
        {
            if ((i >> j & 1) == 0)
                continue;
            for (int k = 0; k < len; k++)
            {
                if (match[k] == '0' && arr[j][k] == '1' ||
                    match[k] == '1' && arr[j][k] == '0')
                {
                    flag = false;
                    break;
                }
                if (match[k] == '?')
                    match[k] = arr[j][k];
            }
        }
        if (!flag)
            continue;
        int tmp = 1;
        for (int j = 0; j < len; j++)
            if (match[j] == '?')
                tmp = (tmp * 2) % MOD;
        bool op = __builtin_popcount(i) & 1; // odd+ even-
        if (op)
            res = (res + tmp) % MOD;
        else
            res = (res - tmp + MOD) % MOD;
    }
    return res;
}

void solve()
{
    int n;
    cin >> n;
    map<int, vector<string>> mp;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        mp[s.length()].emplace_back(s);
    }
    int ans = 0;
    for (auto &[len, arr] : mp)
    {
        if (len <= 20)
            ans = (ans + brute_force(arr)) % MOD;
        else
            ans = (ans + inc_exc(arr)) % MOD;
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}