题目大意
共有 \(N\) 个灯泡，最开始都是不亮的，由 \(M\) 个开关控制，每个开关有各自的控制范围，开关可以让亮的灯不亮，同时让不亮的灯变亮。求这些灯光可能有多少种状态。
问题转化
- 每个开关看作一个长度为 \(N\) 的二进制向量（O 表示 \(1\)，X 表示 \(0\)）。
- 每个灯泡的状态看作一个长度为 \(N\) 的二进制向量。
- 按下开关相当于对当前状态向量进行异或操作。
问题转化为：给定 \(M\) 个 \(N\) 维 \(0/1\) 向量，问这些向量通过异或运算能生成多少个不同的向量。
解题思路
标签：线性基
设向量集合的线性基大小为 \(k\)（即秩），那么：
- 线性基可以生成 \(2^k\) 个不同的向量。
- 每个开关按或不按，正好对应 \(2^M\) 种选择。
- 但不同的选择可能产生相同的结果，所以实际不同的结果数是 \(2^k\)。
时间复杂度
主要来自于高斯消元法：
- 外层循环：最多 \(n\) 次
- 内层循环：寻找和消元各 \(m\) 次
- 总复杂度：\(O(n \times m)\)
对于 \(n, m \leq 50\)，可以接受。
参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;ll n, m;
ll a[520]; // 存储每个开关的二进制表示
ll k = 0; // 线性基的大小（秩）
ll p = 2008; // 高斯消元法求线性基
void Gauss() {// 从高位到低位处理每一位（第62位到第0位）for (ll i = 62; i >= 0; i--) {// 寻找第i位为1的开关for (ll j = k; j < m; j++) {if ((a[j] >> i) & 1LL) { // 如果第j个开关的第i位是1swap(a[j], a[k]); // 交换到第k行break;}}// 如果第i位没有1，继续处理下一位if (((a[k] >> i) & 1LL) == 0LL) continue;// 用第k行消去其他行的第i位for (ll j = 0; j < m; j++) {if (j != k && ((a[j] >> i) & 1LL)) {a[j] ^= a[k]; // 异或消元}}k++; // 成功找到一个基向量，秩加1}
}int main() {cin >> n >> m;string s;// 读入每个开关的控制状态for (ll i = 0; i < m; i++) {cin >> s;// 将字符串转换为二进制数for (ll j = 0; j < n; j++) {if (s[j] == 'O') {a[i] |= (1LL << j); // 第j位设为1}}}// 构建线性基Gauss();ll result = 1;for (ll i = 0; i < k; i++) {result = (result * 2) % p;}cout << result;return 0;
}