扩展了集合幂级数的定义，比较有借鉴性。
题意：三个人玩 $k$ 次石头剪刀布，两个人会分别从自己的策略集合中随机选取一个然后按照选的策略出 $k$ 次（每个策略都是长度为 $k$ 的字符串，代表每次出的是什么）。第一个人策略集合大小为 $n$，第二个人策略集合大小为 $m$。第三个人想知道，对于 $3 ^ k$ 种他出的策略，计算他 $k$ 次中至少有一次成为唯一赢家的概率。$k\leq 12, n, m\leq 3 ^ k$，5s。
容易发现我们当且仅当第一个人和第二个人出的一样，第三个人出的可以赢他们的情况才可能计入答案。
我们考虑构造另外一种状态，记作 0，表示这个人可以随意出。容易发现这个状态是包含 1、2、3 的状态的（分别对应石头剪刀布），那么如果我们使用类似集合幂级数的思想前缀和的话，我们就要将对应 1、2、3 的数贡献到对应位为 0 的数。
类似集合幂级数定义卷积，定义一个运算，使得如果两个数不同，这一位就是 0，否则就是相同的那个数。容易发现无需暴力卷积，我们按照上面的方法先前缀和，乘起来，再做逆变换。
做法的正确性：拆位打开看，如果这两个数对应位相同，假设为 $x$，那么这个的贡献不仅会在该位为 0 的地方出现，还会在该位为 $x$ 的地方出现，乘起来后做逆变换，这样 0 位置的贡献就变为了 0。而如果不一样的话，这两个数对应位不同，这样一个出现的位置是 $0, x$，另一个出现的位置是 $0, y$，这样乘起来后，只出现在 0 的位置，于是贡献到了 0。这个可以看作是一个广义的与卷积。
这样，我们可以用 $O(k4 ^ k)$ 的时间得到每个状态的各处。然后考虑如何得到答案。
经典至少一个容斥为都不是，考虑计算这个状态下不能胜的情况。对于这一位为 1 来说，不能胜的情况就是 0、2、3。特别的，这一位为 0 不能胜的情况是 0、1、2、3，即所有。
还是类似集合幂级数拆位的思想，拆开每一位分别贡献，仍然可以做到 $O(k4 ^ k)$。
最后直接判断这一个状态是不是切实存在的（即所有位都不是 0），输出即可。
注意编号的问题，我们可以先将编号设为 1-石头，2-剪刀，3-布（原来是 1-布，2-石头，3-剪刀），这样就是计算三个人相同的问题了，直接按序输出即可。时间复杂度 $O(k4 ^ k)$。
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
| int trs(char c) { return c == 'P' ? 3 : (c == 'R' ? 1 : 2); }
template <class T>
void FMT(T *a)
{
for (int j = 0; j < k + k; j += 2)
for (int i = 0; i < (1 << (k + k)); ++ i)
if (i >> j & 3) a[i & ~(3 << j)] += a[i];
}
template <class T>
void IFMT(T *a)
{
for (int j = 0; j < k + k; j += 2)
for (int i = 0; i < (1 << (k + k)); ++ i)
if (i >> j & 3) a[i & ~(3 << j)] -= a[i];
}
int main()
{
std::cin >> k >> n >> m;
for (int i = 1; i <= n; ++ i)
{
scanf("%s", tmp + 1);
int s = 0;
for (int i = 1; i <= k; ++ i)
s = (s << 2) | trs(tmp[i]);
A[s] ++;
}
for (int i = 1; i <= m; ++ i)
{
scanf("%s", tmp + 1);
int s = 0;
for (int i = 1; i <= k; ++ i)
s = (s << 2) | trs(tmp[i]);
B[s] ++;
}
FMT(A), FMT(B);
for (int i = 0; i < (1 << (k + k)); ++ i) C[i] = (LL) A[i] * B[i];
IFMT(C);
for (int j = 0; j < (k + k); j += 2)
for (int i = 0; i < (1 << (k + k)); ++ i) {
if (i >> j & 3) continue;
LL sum = C[i] + C[i | (1 << j)] + C[i | (2 << j)] + C[i | (3 << j)];
C[i] = sum;
C[i | (1 << j)] = sum - C[i | (1 << j)];
C[i | (2 << j)] = sum - C[i | (2 << j)];
C[i | (3 << j)] = sum - C[i | (3 << j)];
}
for (int s = 0; s < (1 << (k + k)); ++ s) {
bool flag = true;
for (int i = 0; i < (k + k) && flag; i += 2)
flag &= !!(s >> i & 3);
if (!flag) continue;
printf("%lld\n", (LL) n * m - C[s]);
}
return 0;
}
|