COCI 2021-2022 #1 - Set 题解

思路

我们将原题中的数的每一位减一，此时问题等价。

下面的异或都是在三进制下的异或。（相当于不进位的加法）

我们考虑原题中的条件，对于每一位，如果相同，则异或值为 $0$，如果为 $1$， $2$， $3$ 的排列，则异或值也为 $0$。

于是我们设 $C_k$ 表示有没有 $k$ 这个数，$ans={\sum }_{i\oplus j\oplus k=0}{c}_i\cdot c_j\cdot c_k$，则答案为 $\frac{ans-n}{6}$。

其中 $ans$ 可以用 FWT 求，具体实现可以看我的博客。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, k, len = 1;
LL ans;
complex <double> a[1000005];
const complex <double> w = {-0.5, 0.5 * sqrt(3)}, w2 = {-0.5, -0.5 * sqrt(3)};
int in() {char ch = getchar();int s = 0;while (ch < '0' || ch > '9')ch = getchar();while (ch <= '9' && ch >= '0')s = s * 3 + ch - '1', ch = getchar();return s;
}
void FWT(complex <double> *f, int flag) {for (int mid = 1; mid < len; mid = mid * 3) {for (int i = 0; i < len; i = i + mid * 3) {for (int j = i; j < i + mid; j++) {complex <double> t0 = f[j], t1 = f[j + mid], t2 = f[j + mid * 2];if (flag == 1) {f[j] = t0 + t1 + t2;f[j + mid] = t0 + t1 * w + t2 * w2;f[j + mid * 2] = t0 + t1 * w2 + t2 * w;}else {f[j] = t0 + t1 + t2;f[j + mid] = t0 + t1 * w2 + t2 * w;f[j + mid * 2] = t0 + t1 * w + t2 * w2;double t;t = f[j].real(), f[j].real(t / 3);t = f[j + mid].real(), f[j + mid].real(t / 3);t = f[j + mid * 2].real(), f[j + mid * 2].real(t / 3);t = f[j].imag(), f[j].imag(t / 3);t = f[j + mid].imag(), f[j + mid].imag(t / 3);t = f[j + mid * 2].imag(), f[j + mid * 2].imag(t / 3);}}}}
}
int main() {scanf("%d%d", &n, &k);for (int t = 0; t < k; t++)len = len * 3;for (int i = 0; i < n; i++)a[in()].real(1);FWT(a, 1);for (int i = 0; i < len; i++)a[i] = a[i] * a[i] * a[i];FWT(a, -1);ans = a[0].real() + 0.5;printf("%lld\n", (ans - n) / 6);return 0;
}