没见过这种在新运算下做卷积的题，感觉挺新奇的。
考虑 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 每种策略的数量，那么实际上我们希望先求：
\[c_i = \sum\limits_{j \otimes k = i} a_j b_k \]这个东西是可以 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;
}