首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

HDU 3364 Lanterns:高斯消元解開關燈泡方案數

     編輯:關於C++

問題描述

m 個開關控制 n 個燈泡,開關可翻轉對應燈泡狀態。給定燈泡目標狀態,求開關組合數。模 2 線性方程組:A * x = b (mod 2)。解的個數 = 2^{free_vars}(若有解)。

高斯消元 (模 2)

  • 增廣矩陣 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 個變量係數。
  • 模 2 下 XOR 即減法,無需乘法逆元。
  • 多查詢共用係數矩陣,僅常數項變化,預存 b 每次拷貝。
  • 答案可能大,用 long long(2^60 超出則需大整數,但題目約束較小)。

總結

HDU 3364 是「開關燈泡 → 模 2 線性方程組 → 高斯消元」的標準套路。關鍵在於正確建立係數矩陣(開關-燈泡關係),並利用模 2 性質簡化消元(XOR 替代除法)。自由變量計數給出方案數指數級增長。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved