m 個開關控制 n 個燈泡,開關可翻轉對應燈泡狀態。給定燈泡目標狀態,求開關組合數。模 2 線性方程組:A * x = b (mod 2)。解的個數 = 2^{free_vars}(若有解)。
a[equ][var+1],最後一列為常數項 b。XOR 消零。0 = 1 行。var - rank,答案 = 2^{free}。int a[60][60], b[60][60], x[60], free_x[60];
int equ, var;
int Gauss() {
memset(free_x,0,sizeof(free_x));
int row=0, col=0;
for (; rowabs(a[max_r][col])) max_r=i;
if (max_r!=row) for (int j=col;j<=var;j++) swap(a[max_r][j],a[row][j]);
if (a[row][col]==0) { row--; continue; }
for (int i=row+1;i
a[i][j] 表示第 i 條方程第 j 個變量係數。XOR 即減法,無需乘法逆元。b 每次拷貝。long long(2^60 超出則需大整數,但題目約束較小)。HDU 3364 是「開關燈泡 → 模 2 線性方程組 → 高斯消元」的標準套路。關鍵在於正確建立係數矩陣(開關-燈泡關係),並利用模 2 性質簡化消元(XOR 替代除法)。自由變量計數給出方案數指數級增長。