題目大意：給出一個 n * n 的布爾矩陣表示開關(guān)與燈的關(guān)系，現(xiàn)在每個燈來說，是否存在一種開關(guān)的集合，使得恰好使得只有當(dāng)前燈是打開狀態(tài)，其余燈都是熄滅狀態(tài)，分別輸出方案

題目分析：將開關(guān)視為變元，將燈視為方程，這樣就將問題轉(zhuǎn)換為了求 n 次線性方程組，最樸素的方法就是枚舉 n 次常數(shù)項，每次都對線性方程組進(jìn)行求解，可惜這樣的時間復(fù)雜度是 O( n^4 )

考慮優(yōu)化，設(shè) A 為系數(shù)矩陣，X 為未知量矩陣，B 為常數(shù)矩陣，則線性方程組轉(zhuǎn)換為了 ，移項可得?

這樣問題就轉(zhuǎn)換為了求出系數(shù)矩陣的逆矩陣，然后 O( n ) 枚舉常數(shù)矩陣，利用矩陣乘法求解即可，矩陣乘法是 O( n^3?) 的，但由于常數(shù)矩陣 B 只有一維，所以矩陣乘法的實際復(fù)雜度是 O( n^2 )，這樣總時間復(fù)雜度就是 O( n^3 )

最后補充一下，比較顯然的是，如果系數(shù)矩陣沒有逆矩陣的話，那么肯定是無解的

代碼：

#pragma GCC optimize(2) #pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=505;const int mod=2;int n;LL a[N][N<<1];LL q_pow(LL a,LL b) {LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; }bool Gauss_j() {for(int i=1,r;i<=n;i++){r=i;for(int j=i+1;j<=n;j++)if(a[j][i]>a[r][i])r=j;if(r!=i)swap(a[i],a[r]);if(!a[i][i])return false;int kk=q_pow(a[i][i],mod-2);for(int k=1;k<=n;k++){if(k==i)continue;int p=a[k][i]*kk%mod;for( int j=i;j<=(n<<1);j++)a[k][j]=((a[k][j]-p*a[i][j])%mod+mod)%mod;}for(int j=1;j<=(n<<1);++j) a[i][j]=(a[i][j]*kk%mod);}return true; }struct Matrix {long long a[N][N];int x,y;//長寬Matrix operator * (const Matrix &B)//矩陣乘法{Matrix tmp;for (int i = 0; i < x; ++ i)for (int j = 0; j < B.y; ++ j){tmp.a[i][j] = 0;for (int k = 0; k < y; ++ k){tmp.a[i][j] = (tmp.a[i][j] + a[i][k] * B.a[k][j] % mod) % mod;}}tmp.x = x;tmp.y=B.y;return tmp;} }inv,B,ans;int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d",&n);for(int i=1;i<=n;i++){a[i][i+n]=1;for(int j=1;j<=n;j++)scanf("%d",&a[j][i]);}if(Gauss_j()){inv.x=inv.y=n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)inv.a[i-1][j-1]=a[i][j+n];B.x=n,B.y=1;for(int i=0;i<n;i++){for(int j=0;j<n;j++)B.a[j][0]=(i==j);ans=inv*B;for(int j=0;j<n;j++)if(ans.a[j][0])printf("%d ",j+1);puts("");}}elseputs("-1");return 0; }

?

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的中石油训练赛 - Switches(高斯消元求逆矩阵+逆矩阵求线性方程组)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。