题目分析

给定一个在 $\{-1, +1\}^N$ 上定义的布尔函数 $f$，我们需要找到其唯一的多线性多项式表示。由于输入信号的平方为 1，多项式不含幂次项，共有 $2^N$ 个可能的项。

例如，对于 $N=2$ 的情况，多项式形式为：

$$f(x_1,x_2) = c_0 + c_1x_1 + c_2x_2 + c_3x_1x_2$$

解题思路

使用快速沃尔什-哈达玛变换 (FWHT) 将真值表转换为多项式系数：

1. 数学原理：在 $\{-1, +1\}$ 域上，FWHT 可以高效计算多项式的系数
2. 算法选择：FWHT 的时间复杂度为 $O(N \cdot 2^N)$，适合 $N \leq 20$ 的数据范围
3. 数值处理：将浮点数转换为整数运算，避免精度误差

关键算法

FWHT 变换

对于哈达玛矩阵 $H = \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix}$，递归应用蝴蝶操作：

for 每个块大小 i = 1,2,4,...,2^(n-1)
    for 每个块起始位置 j
        for 块内每个位置 k
            a = f[j+k], b = f[j+i+k]
            f[j+k] = a + b
            f[j+i+k] = b - a

输出顺序

按字典序输出：常数项、单变量项、双变量项等，变量下标递增。

完整代码

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

constexpr int N = 1 << 20;  // 最大状态数 2^20
constexpr int M = 55;       // 最大输入字符串长度

int f[N];  // 存储函数值和变换后的系数
int n, m;  // n: 变量数, m: 状态数 2^n
char s[M]; // 输入字符串缓冲区

// 输出多项式项：格式化系数和变量
void Pr(int x, int t) {
    if (!x) return;  // 系数为0，不输出
    
    // 处理负号
    if (x < 0) {
        cout << '-';
        x = -x;
    }
    
    // 计算最简分数形式
    int g = __gcd(x, 100 << n);
    
    if (g == (100 << n)) {
        // 系数为整数
        cout << x / g;
    } else {
        // 输出分数形式
        cout << x / g << '/' << (100 << n) / g;
    }
    
    // 输出变量部分
    cout << ' ';
    for (int i = 1; i <= n; i++) {
        if (t >> (n - i) & 1) {
            cout << "x" << i;
        }
    }
    cout << endl;
}

// 递归输出多项式项，按字典序
void out(int x, int d) {
    // 输出当前项
    Pr(f[(d << 1 | 1) << (n - x)], (d << 1 | 1) << (n - x));
    
    // 递归终止条件
    if (x == n) return;
    
    // 先输出包含当前变量的项，再输出不包含的
    out(x + 1, d << 1 | 1);  // 包含 x_{x+1}
    out(x + 1, d << 1);      // 不包含 x_{x+1}
}

int main() {
    // 读取输入
    scanf("%d", &n);
    m = 1 << n;  // 状态总数
    
    // 读取真值表
    for (int T = 0, i; T < m; T++) {
        double g;
        i = 0;
        scanf(" %s %lf", s, &g);
        
        // 将"++-+"字符串转换为二进制索引
        for (int j = 0; j < n; j++) {
            i = i << 1 | (s[j] == '+');
        }
        
        // 将浮点数转换为整数（乘以100避免浮点误差）
        f[i] = int(g < 0 ? g * 100 - 0.5 : g * 100 + 0.5);
    }
    
    // 执行快速沃尔什-哈达玛变换
    for (int i = 1; i < (1 << n); i <<= 1) {
        for (int j = 0; j < (1 << n); j += i << 1) {
            for (int k = 0; k < i; k++) {
                int a = f[j + k];
                int b = f[j + i + k];
                f[j + k] = a + b;
                f[j + i + k] = b - a;
            }
        }
    }
    
    // 输出多项式系数
    Pr(f[0], 0);  // 常数项
    out(1, 0);    // 其他项（按字典序）
    
    return 0;
}

代码说明

主要函数：

1. Pr(x, t)：输出单项式

   • x：系数（已乘以 $100 \cdot 2^n$）
   • t：变量掩码，指示包含哪些变量

2. out(x, d)：递归输出所有项

   • 按字典序：常数项 → 单变量 → 双变量 → ...
   • 变量下标递增

3. FWHT 实现：

   • 三层循环实现蝴蝶操作
   • 原地变换，节省空间

关键技巧：

• 精度处理：将浮点数乘以100转换为整数运算
• 位运算：用二进制位表示变量组合
• 字典序输出：通过递归顺序自然实现

数学背景

FWHT 对应的变换矩阵是哈达玛矩阵的 $n$ 次张量积：

$$H^{\otimes n} = \underbrace{H \otimes H \otimes \cdots \otimes H}_{n\text{次}} $$

变换公式：

$$\text{coefficients} = \frac{1}{2^n} H^{\otimes n} \cdot \text{truth table} $$

代码中省略了除以 $2^n$ 的缩放，在输出时通过分母体现。

复杂度分析

• 时间复杂度：$O(N \cdot 2^N)$
  • FWHT：$O(N \cdot 2^N)$
  • 输出：$O(2^N)$
• 空间复杂度：$O(2^N)$