仿做靜態(tài)網(wǎng)站多少錢(qián)seo網(wǎng)址超級(jí)外鏈工具
題目:
登錄—專(zhuān)業(yè)IT筆試面試備考平臺(tái)_??途W(wǎng)
思路:
我們發(fā)現(xiàn)對(duì)于矩陣C可以一列一列求。
mod2,當(dāng)這一行相乘1的個(gè)數(shù)為奇數(shù)時(shí),z(i,j)為1,偶數(shù)為0,是異或消元。
對(duì)于b[i,j]*c[i,j],b[i,j]可以與a[i,i]異或讓他轉(zhuǎn)換到左邊,而右邊一列全為0。
每一列的解是不能確定元素cn個(gè)的2^cn。
異或消元可以用bitset優(yōu)化。
代碼:
#include <iostream>
#include<map>
#include<queue>
#include<unordered_map>
#include<cmath>
#include<bitset>
using namespace std;
#define LL long long
const int N=1e3+100;
double eps=1e-12;
const long long mod=998244353;
std::bitset<210> A[210],a[210],b[210];
int n;
LL quick(LL a,LL b,LL mod){
? ?LL ans=1;
? ?while(b){
? ? if(b&1) ans=ans*a%mod;
? ? b>>=1;
? ? a=a*a%mod;
? ?}
? ?return ans;
}
LL guss()
{ ? int c=1,r=1;
? ?for(c=1;c<=n;c++)
? ?{ ?int t=r;
? ? for(int i=r+1;i<=n;i++) if(a[i][c]>a[t][c]) t=i;
? ? ?if(!a[t][c]) continue;
? ? swap(a[t],a[r]);
? ? for(int i=r+1;i<=n;i++)
? ? ? ? if(a[i][c])
? ? ? ? a[i]=a[i]^a[r];
? ? ? r++;
? ?}
? ?return quick(2,n-r+1,mod);
}
int main()
{ ?cin>>n;
? for(int i=1;i<=n;i++)
? for(int j=1;j<=n;j++)
? { ?int x;
? ? ? scanf("%d",&x);
? ? ? if(x) A[i][j]=1;
? }
? for(int i=1;i<=n;i++)
? for(int j=1;j<=n;j++)
? { ?int x;
? ? ? scanf("%d",&x);
? ? ? if(x) b[i][j]=1;
? }
? ?LL ans=1;
? ?for(int j=1;j<=n;j++)
? ?{
? ? ?for(int i=1;i<=n;i++)
? ? ?for(int k=1;k<=n;k++)
? ? ?a[i][k]=A[i][k];
? ? ?for(int i=1;i<=n;i++) a[i][n+1]=0;
? ? ?for(int i=1;i<=n;i++)
? ? ?a[i][i]=a[i][i]^b[i][j];
? ? ?ans=ans*guss()%mod;
? ?}
? ?cout<<ans<<endl;
? ? return 0;
}
?