原题呈现

P7670 毒蛇越狱 / Snake Escaping#

题目描述#

JOI 实验室有 $2^L$ 条毒蛇．蛇的编号为 $0,1,\cdots,2^L−1$ ．每条蛇从头到尾分为 $L$ 个部分．每个部分的颜色是蓝色或红色．对于毒蛇 $i$ ，令 $i = \sum_{k=1}^{L} c_k2^{L-k}$ （ $0 \leq c_k \leq 1$ ）为 $i$ 的二进制表达式．那么，

如果 $c_k=0$ ，毒蛇 $i$ 从头开始的第 $k$ 部分的颜色是蓝色，
如果 $c_k=1$ ，毒蛇 $i$ 从头开始的第 $k$ 部分的颜色是红色．

每条毒蛇都有一个 $0$ 到 $9$ 之间的整数，包括 $0$ 和 $9$ ，为毒性．给出一个由 $\texttt{0,1,2,3,4,5,6,7,8,9}$ 组成的长度为 $2^L$ 的字符串 $S$ ．第 $i$ 个字符（ $1 \leq i \leq 2^L$ ）是毒蛇 $i−1$ 的毒性．由于毒蛇行动迅速，所以经常从 JOI 实验室逃走．住在实验室附近的人向 JOI 实验室投诉，他们看到毒蛇从实验室逃逸．您将收到 $Q$ 天的投诉清单．第 $d$ 天的投诉（ $1 \leq d \leq Q$ ）是一个长度为 $L$ 的字符串 $T_d$ ，由 $\texttt{0,1,?}$ 组成．

如果 $T_d$ 的第 $j$ 个字符（ $1 \leq j ≤ L$ ）为 $\texttt{0}$ ，这意味着第 $d$ 天从实验室逃出的每条毒蛇的第 $j$ 个部分是蓝色的，
如果 $T_d$ 的第 $j$ 个字符（ $1 \leq j \leq L$ ）为 $\texttt{1}$ ，这意味着第 $d$ 天从实验室逃出的每条毒蛇的第 $j$ 部分是红色的，并且
如果 $T_d$ 的第 $j$ 个字符（ $1 \leq j \leq L$ ）为 $\texttt{?}$ ，这意味着人们没有提供关于第 $d$ 天从实验室逃逸的毒蛇的第 $j$ 部分的信息．

所有的投诉都是准确的信息．所有从实验室逃逸的毒蛇都在同一天被 JOI 实验室的工作人员收留．可能发生同一条蛇在不同的日子逃脱． JOI 实验室执行主任 K 教授为了估计毒蛇逃逸的风险，想知道可能逃出实验室的毒蛇的毒性总和．你的任务是编写一个程序，根据 $Q$ 天的投诉列表，计算每天可能从实验室逃逸的蛇的毒性总和．现给定描述毒蛇毒性的字符串 $S$ 和 $Q$ 天的投诉列表，请编写一个程序来计算每天可能从实验室逃逸的蛇的毒性总和．

输入格式#

第一行包含两个空格分隔的整数 $L$ ， $Q$ ，分别是每条毒蛇的部位数和投诉天数．第二行包含长度为 $2^L$ 的字符串 $S$ ，描述了毒蛇的毒性．后面 $Q$ 行的第 $d$ 行包含一个长度为 $L$ 的字符串 $T_d$ ，为第 $d$ 天的投诉．

输出格式#

共 $Q$ 行，第 $d$ 行应包含一个整数，即第 $d$ 天可能从实验室逃逸的蛇的毒性总和．

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

1
4 8
2
3141592653589793
3
0101
4
?01?
5
??1?
6
?0??
7
1?00
8
01?1
9
??10
10
????

输出 #2#

说明/提示#

数据规模与约定#

对于 $100 \%$ 的数据， $1 \leq L \leq 20$ ， $1 \leq Q \leq 10^6$ ， $S$ 是长度为 $2^L$ 的字符串，字符串 $S$ 由 $\texttt{0,1,2,3,4,5,6,7,8,9}$ 组成， $T_d$ 是长度为 $L$ （ $1 \leq d \leq Q$ ）的字符串，字符串 $T_d$ 由 $\texttt{0,1,?}$ （ $1 \leq d \leq Q$ ）组成．

Subtask $1$ （ $5$ points）： $L \leq 10$ ， $Q \leq 1000$ ．
Subtask $2$ （ $7$ points）： $L \leq 10$ ．
Subtask $3$ （ $10$ points）： $L \leq 13$ ．
Subtask $4$ （ $53$ points）： $Q \leq 5000$ ．
Subtask $5$ （ $25$ points）：没有额外的限制．

样例说明#

对于样例 $1$ ： $L=3$ ，共 $2^3=8$ 条毒蛇，它们中的每一条都分为 $3$ 个部分．投诉时间为 $5$ 天．

第一天，可能逃出实验室的毒蛇只有毒蛇 $0$ ．毒性总和为 $1$ ．
第二天，可能从实验室逃逸的毒蛇是毒蛇 $0,1,2,3$ ．毒性总和为 $10$ ．
第三天，可能从实验室逃逸的毒蛇是毒蛇 $4,6$ ．毒性总和为 $12$ ．
第四天，可能从实验室逃逸的毒蛇是毒蛇 $3,7$ ．毒性总和是 $12$ ．
第五天，可能从实验室逃逸的毒蛇是毒蛇 $0,1,2,3,4,5,6,7$ ．毒性总和为 $36$ ．

此题题意就是给定一个模式串，求二进制表示匹配这个模式串的所有数权值之和．

最容易想到的就是枚举所有问号部分应该填什么，然后将所有可能的数字权值加起来．下面的程序实现了这个暴力．其中，

A 的二进制上每一位是 1，当且仅当模式串上这一位是 0．
B 的二进制上每一位是 1，当且仅当模式串上这一位是 1．
C 的二进制上每一位是 1，当且仅当模式串上这一位是 ?．

1
// 枚举 T，T 表示我们钦定这些部分应该填 1
2
for (int T = C; T > 0; T = (T - 1) & C) {
3
  int U = B | T;
4
  ans += w[U];
5
}
6
ans += w[B];

程序的复杂度高达 $O(q2^L)$ ，需要优化．

在复杂度中， $L$ 在指数位上，只需要让 $L\leq 8$ 就可以了．因此，对于问号数量小于等于 8 的模式串，可以使用上面的暴力．那对于问号数量大于 8 的呢？问号数量既然大于 8，由于 $L\leq 20$ ，那么必然会有 1 的数量小于 8，或者 0 的数量小于 8．对于这两种情况分别考虑．

对于 0 的数量小于 8 的情况，我们可以尝试使用容斥．具体来说，对于每一个为 0 的位置，设其组成一个集合，即为上述的 $A$ ，则满足条件的情况为：模式串中每一个规定为 0 的位置都全部遵守的权值，减去钦定有一个位置不遵守的权值，加上有钦定两个位置不遵守的权值……公式化的，设钦定模式串中为 0 的位置必须为 1 的位置集合是 $T$ ，则有：

ans=\sum_{T\subseteq A}((-1)^{|T|}g(B\cup T))

其中， $B$ 的含义为上文所述，故 $B\cup T$ 的含义为当前钦定限制下，所有必须为 1 的位置集合， $g(x)$ 表示超集和，即所有满足以下条件的数字 $y$ 的权值和：

若设 $a$ 的从右到左第 $i$ 个二进制位为 $a_i$ ，则当 $x_i=1$ 时， $y_i=1$ ．即 $x$ 中为 1 的位 $y$ 中也必须为 1．

公式化的，其统计的是 $\sum_{T\supseteq x}w(T)$ ．

$g(x)$ 可以通过高维后缀和预处理出来，在后文会详细说明．

1
// 枚举 T，T 表示我们钦定这些部分应该填 1，即使模式串中为 0
2
for (int T = A; T > 0; T = (T - 1) & A) {
3
  int U = B | T;
4
  if (__builtin_popcount(T) & 1) {
5
    ans -= g[U];
6
  } else {
7
    ans += g[U];
8
  }
9
}
10
ans += g[B];

对于 1 的数量小于 8 的情况，我们可以仍可以像处理 0 一样使用容斥．具体来说，对于每一个为 1 的位置，设其组成一个集合，即为上述的 $B$ ，则满足条件的情况为：模式串中每一个规定为 1 的位置都全部遵守的权值，减去钦定有一个位置不遵守的权值，加上有钦定两个位置不遵守的权值……公式化的，设钦定模式串中为 1 的位置必须为 0 的位置集合是 $T$ ，则有：

ans=\sum_{T\subseteq B}[(-1)^{|T|}f((A\cup T)^c)]

其中， $A\cup T$ 的含义为当前钦定限制下，所有必须为 0 的位置集合，因此 $(A\cup T)^c$ 就是 $A\cup T$ 的补集，其代表所有可以为 1 的位置集合， $f(x)$ 表示子集和，即所有满足以下条件的数字 $y$ 的权值和：

若设 $a$ 的从右到左第 $i$ 个二进制位为 $a_i$ ，则当 $x_i=0$ 时， $y_i=0$ ．即 $x$ 中为 0 的位 $y$ 中也必须为 0．

公式化的，其统计的是 $\sum_{T\subseteq x}w(T)$ ．

$f(x)$ 可以通过高维前缀和预处理出来，在后文会详细说明．

1
int U = (1 << n) - 1;
2
// 枚举 T，T 表示我们钦定这些部分应该填 0，即使模式串中为 1
3
for (int T = B; T; T = (T - 1) & B) {
4
  int NA = A | T;
5
  int Com = U ^ NA;
6
  if (__builtin_popcount(T) & 1) {
7
    ans -= f[Com];
8
  } else {
9
    ans += f[Com];
10
  }
11
}
12
int Com = U ^ A;
13
ans += f[Com];

最后，对于 $f(x)$ 和 $g(x)$ 的预处理，可以使用高维前后缀和．

我们知道，对于一维的前缀和，其转移方程是这样的：

1
for(int i = 1; i <= n; i++)
2
  a[i] += a[i-1];

而对于二维，可以使用容斥，也可以一维一维地求：

1
for(int i = 1; i <= n; i++)
2
    for(int j = 1; j <= n; j++)
3
        a[i][j] += a[i - 1][j];
4
for(int i = 1; i <= n; i++)
5
  for(int j = 1; j <= n; j++)
6
    a[i][j] += a[i][j - 1];

对于高维前缀和，可以将其视作多维前缀和，这里 $n=20$ ，就是 20 维空间，每一维的大小是 2，即只有 0 和 1 两种状态．我们对于每一个维度，都尝试将 0 的统计值加到 1 的头上．高维后缀和正好相反，它尝试将 1 的统计值加到 0 的头上．

可以使用下面的代码，时间复杂度 $O(n2^n)$ ．

1
for (int i = 0; i < n; i++) { // 枚举维度
2
  for (int T = 0; T < (1 << n); T++) { // 枚举所有的状态
3
    if (T >> i & 1) { // 如果第 i 位是 0
4
      // 就把状态加到同维 1 的头上
5
      f[T] += f[T ^ (1 << i)];
6
    } else { // 如果第 i 位是 1
7
      // 就把状态加到同维 0 的头上
8
      g[T] += g[T ^ (1 << i)];
9
    }
10
  }
11
}

整体的复杂度为 $O(n2^n+\sqrt[3]{q2^L})$ ，这种分类讨论是一种分治技巧，常称之为根号分治．

标程

1
#define IO(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int N = 2e6 + 100;
5
int n, q, w[N], f[N], g[N];
6
int A, B, C, ans;
7

8
void solve_A() {
9
    // 0 居少
10
    // 枚举必须为 0 中为 1 的位置
11
    for (int T = A; T > 0; T = (T - 1) & A) {
12
        int U = B | T;
13
        if (__builtin_popcount(T) & 1) {
14
            ans -= g[U];
15
        } else {
16
            ans += g[U];
17
        }
18
    }
19
    ans += g[B];
20
}
21

22
void solve_B() {
23
    // 1 较少
24
    // 枚举必须为 0 的位置
25
    int U = (1 << n) - 1;
26
    for (int T = B; T; T = (T - 1) & B) {
27
        int NA = A | T;
28
        int Com = U ^ NA;
29
        if (__builtin_popcount(T) & 1) {
30
            ans -= f[Com];
31
        } else {
32
            ans += f[Com];
33
        }
34
    }
35
    int Com = U ^ A;
36
    ans += f[Com];
37
}
38

39
void solve_C() {
40
    // 问号居少，暴力
41
    for (int T = C; T > 0; T = (T - 1) & C) {
42
        int U = B | T;
43
        ans += w[U];
44
    }
45
    ans += w[B];
46
}
47

48
signed main() {
49
    ios::sync_with_stdio(false);
50
    cin.tie(0);
51
    cout.tie(0);
52
    cin >> n >> q;
53
    string str;
54
    cin >> str;
55
    for (int i = 0; i < (1 << n); i++) {
56
        w[i] = str[i] - '0';
57
        f[i] = g[i] = w[i];
58
    }
59
    for (int i = 0; i < n; i++) {
60
        for (int T = 0; T < (1 << n); T++) {
61
            if (T >> i & 1) {
62
                f[T] += f[T ^ (1 << i)];
63
            } else {
64
                g[T] += g[T ^ (1 << i)];
65
            }
66
        }
67
    }
68
    while (q--) {
69
        string str;
70
        cin >> str;
71
        A = 0, B = 0, C = 0, ans = 0;
72
        for (int i = 0; i < str.size(); i++) {
73
            char ch = str[n - i - 1];
74
            if (ch == '0') {
75
                A |= (1 << i);
76
            } else if (ch == '1') {
77
                B |= (1 << i);
78
            } else {
79
                C |= (1 << i);
80
            }
81
        }
82
        if (__builtin_popcount(A) <= n / 3) {
83
            solve_A();
84
        } else if (__builtin_popcount(B) <= n / 3) {
85
            solve_B();
86
        } else {
87
            solve_C();
88
        }
89
        cout << ans << endl;
90
    }
91
    return 0;
92
}

音乐

音乐

P7670 毒蛇越狱 / Snake Escaping#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

说明/提示#

数据规模与约定#

样例说明#

文章分享

音乐

安吉D17 T4

P7670 毒蛇越狱 / Snake Escaping#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

说明/提示#

数据规模与约定#

样例说明#

文章分享