没见过这种在新运算下做卷积的题,感觉挺新奇的。
考虑 Takahashi 成为绝对赢家的必要条件,发现前提是 Aoki 和 Snuke 出的要相同。不妨将每种策略映射到一个四进制数(\(P \to 1, R \to 2, S \to 3\)),定义运算 \(x \otimes y = \begin{cases} x & x = y \\ 0 & x \ne y \end{cases}\),设 \(a_i, b_i\) 分别为 Aoki 和 Snuke 每种策略的数量,那么实际上我们希望先求:
这个东西是可以 FWT 算的。先算 \(A_i = \sum\limits_{j \otimes i = i} a_j, B_i = \sum\limits_{j \otimes i = i} b_j\),那么 \(C_i = A_i B_i\),最后 \(C \to c\) IFWT 回去。定义一种新的集合从属关系 \(0 \subset 1, 0 \subset 2, 0 \subset 3\) 且 \(1,2,3\) 互不相交,那么 FWT 的过程相当于做一个超集和。
那么得到了 \(c_i\) 之后,我们还希望求 \(d_i = \sum\limits_{j \otimes i \ne 0} c_j\)。正着算不好算,考虑变成求 \(d_i = \sum\limits_{j \otimes i = 0} c_j\)。考虑设计一个 dp,\(f_{k,i}\) 表示考虑了前 \(k\) 位,\(i\) 表示前 \(k\) 位是已经确定的策略,后面的位和 \(d_i = \sum\limits_{j \otimes i = 0} c_j\) 中的 \(j\) 后面的位相同,这样的方案数。转移枚举在当前位填 \(1/2/3\),并且不能与 \(j\) 在这个位相同。
这样就做完了,时间复杂度 \(O(k 4^k)\)。
code
// Problem: F - Takahashi The Strongest
// Contest: AtCoder - AtCoder Regular Contest 132
// URL: https://atcoder.jp/contests/arc132/tasks/arc132_f
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 15;
const int maxm = (1 << 24) + 50;
int n, m, K, all;
ll f[maxm], g[maxm], h[2][maxm];
inline void FWT(ll *f, ll op) {
for (int k = 1; (k << 2) <= all; k <<= 2) {
for (int i = 0; i < all; i += (k << 2)) {
for (int j = 0; j < k; ++j) {
f[i + j] += (f[i + j + k] + f[i + j + k * 2] + f[i + j + k * 3]) * op;
}
}
}
}
void solve() {
scanf("%d%d%d", &K, &n, &m);
all = (1 << (K * 2));
for (int _ = 0; _ < n; ++_) {
char s[15];
scanf("%s", s);
int x = 0;
for (int i = 0; i < K; ++i) {
if (s[K - i - 1] == 'R') {
x += (1 << (i * 2));
} else if (s[K - i - 1] == 'S') {
x += (2 << (i * 2));
} else {
x += (3 << (i * 2));
}
}
++f[x];
}
for (int _ = 0; _ < m; ++_) {
char s[15];
scanf("%s", s);
int x = 0;
for (int i = 0; i < K; ++i) {
if (s[K - i - 1] == 'R') {
x += (1 << (i * 2));
} else if (s[K - i - 1] == 'S') {
x += (2 << (i * 2));
} else {
x += (3 << (i * 2));
}
}
++g[x];
}
FWT(f, 1);
FWT(g, 1);
for (int i = 0; i < all; ++i) {
f[i] *= g[i];
}
FWT(f, -1);
for (int i = 0; i < all; ++i) {
h[0][i] = f[i];
}
for (int i = 0, o = 0; i < K; ++i, o ^= 1) {
mems(h[o ^ 1], 0);
for (int S = 0; S < all; ++S) {
if (!h[o][S]) {
continue;
}
for (int j = 1; j <= 3; ++j) {
int T = S - (((S >> (i * 2)) & 3) << (i * 2)) + (j << (i * 2));
if (S != T) {
h[o ^ 1][T] += h[o][S];
}
}
}
}
for (int S = 0; S < all; ++S) {
bool flag = 1;
for (int i = 0; i < K; ++i) {
if (((S >> (i * 2)) & 3) == 0) {
flag = 0;
break;
}
}
if (flag) {
printf("%lld\n", 1LL * n * m - h[K & 1][S]);
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Takahashi Strongest AtCoder Regular Contesttakahashi strongest atcoder regular atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder subsegments atcoder regular contest