题目解法：快速沃尔什变换（FWT）在三维情况下的应用

问题分析

题目要求统计满足特定条件的三元组数量，对于每个维度 $z$，三个元素要么全等，要么两两不同。这相当于在三维特征空间中寻找特定的模式。

关键转化

将每个 $m$ 元组看作一个 $m$ 维向量，每个维度取值 ${0,1,2}$。条件可以重新表述为：对于每个维度，三个值的和在模 3 意义下为 0。

算法思路

1.数学建模

• 将字符串映射为三进制数

• 定义变换 $f[op] = \sum_{x} [x \cdot op \equiv 0 \pmod{3}] \cdot cnt[x]$

• 使用三维快速沃尔什变换（FWT）高效计算

2.核心步骤

步骤 1：初始化

• 构建大小为 $3^m$ 的数组

• 统计每个三进制模式的出现次数

步骤 2：快速变换

• 实现三维 FWT，使用三次单位根 $w$（满足 $w^3=1$）

• 通过分治实现 $O(3^m \cdot m)$ 的卷积计算

步骤 3：结果计算

• 计算卷积后，根据变换性质统计满足条件的三元组数量

• 需要去重并除以 $3! = 6$

复杂度分析

• 空间复杂度：$O(3^m)$，其中 $m \leq 12$，$3^{12} = 531441$

• 时间复杂度：$O(3^m \cdot m)$，可接受

• 相比暴力 $O(n^3)$ 有巨大优化

AC代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 三元数结构，用于三维FWT
struct Triple {
    ll a, b;  // 表示为 a + b*w，其中 w^3=1, w^2=-1-w
    Triple(ll x = 0, ll y = 0) : a(x), b(y) {}
    
    Triple operator+(const Triple& other) const {
        return Triple(a + other.a, b + other.b);
    }
    
    Triple operator*(const Triple& other) const {
        return Triple(a * other.a - b * other.b, 
                     a * other.b + other.a * b - b * other.b);
    }
};

const Triple W = Triple(0, 1);      // 单位根 w
const Triple W2 = Triple(-1, -1);   // w^2

using VectorTriple = vector<Triple>;

// 快速三元变换
void fastTripleTransform(VectorTriple& a, bool inverse) {
    int n = a.size();
    
    for (int step = 1; step < n; step *= 3) {
        for (int i = 0; i < n; i += 3 * step) {
            for (int j = i; j < i + step; j++) {
                Triple& x = a[j];
                Triple& y = a[j + step];
                Triple& z = a[j + 2 * step];
                
                if (inverse) {
                    // 逆变换
                    Triple nx = x + y + z;
                    Triple ny = x + W * y + W2 * z;
                    Triple nz = x + W2 * y + W * z;
                    x = nx, y = ny, z = nz;
                } else {
                    // 正变换
                    Triple nx = x + y + z;
                    Triple ny = x + W2 * y + W * z;
                    Triple nz = x + W * y + W2 * z;
                    x = nx, y = ny, z = nz;
                }
            }
        }
    }
    
    // 逆变换需要归一化
    if (inverse) {
        for (auto& x : a) {
            x.a /= n;
            x.b /= n;
        }
    }
}

// 卷积计算
VectorTriple convolution(VectorTriple a, VectorTriple b) {
    fastTripleTransform(a, false);
    fastTripleTransform(b, false);
    
    for (int i = 0; i < a.size(); i++) {
        a[i] = a[i] * b[i];
    }
    
    fastTripleTransform(a, true);
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // 计算变换空间大小
    int size = 1;
    for (int i = 0; i < m; i++) {
        size *= 3;
    }
    
    VectorTriple count(size);
    vector<int> opCount(size);
    
    // 读入数据并统计
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        
        int value = 0, op = 0;
        
        for (char c : s) {
            int digit = c - '1';  // 将'1','2','3'映射为0,1,2
            value = 3 * value + digit;
            op = 3 * op + ((3 - digit) % 3);  // 计算对应的操作数
        }
        
        count[value].a++;
        opCount[op]++;
    }
    
    // 计算卷积
    VectorTriple convResult = convolution(count, count);
    
    // 统计结果
    ll answer = 0;
    for (int i = 0; i < size; i++) {
        answer += convResult[i].a * opCount[i];
    }
    
    // 去重：减去单个元素的情况，除以排列数
    answer -= n;
    answer /= 6;
    
    cout << answer << '\n';
    
    return 0;
}