题目链接:A-Matrix Equation_第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南) (nowcoder.com)
题意:给我们两个个n行n列的矩阵A和矩阵B,让我们求出来满足A×C=B⊙C的矩阵C的个数。
设B⊙C=D,则有D( i , j )=B( i , j )*C( i , j )
我一开始的想法是设出C矩阵,然后写出A×C以及B⊙C,然后使得结果矩阵的对应值相等,这样就得到一个n*n个方程的方程组,我们就可以用高斯消元来对这个方程组进行求解,求出来*元的个数,然后答案就是2^(*元),但是这样做的复杂度是o(n^6 / 3),这样显然是会超时的,这个时候我们就要想其他的方法了,我们结合线性代数中的知识可以知道有下面这个性质:
这样我们就可以把X矩阵化成列矩阵(x1,x2,……,xn),然后单独判断每一个n个方程组成的方程组A×xi=Bi×xi,这样复杂度就变为了n*n^3/3=n^4/3,这样复杂度还是有点超,由于这是异或方程,我们可以使用bitset进行优化,大概能把空间和时间都减少为原来的1/32(高斯消元中的互换行之前需要一个一个操作,而现在可以一行一块操作),这样复杂度就满足题目要求了。
下面是代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<bitset>
using namespace std;
const int N=220,mod=998244353;
#define int long long
int a[N][N],B[N],b[N][N],n;
bitset<N>c[N];
int qmi(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int calc()
{
for(int i=1,row=1;i<=n;i++)
{
int k=row;
for(;k<=n;k++)
if(c[k][i])
break;
if(k>n) continue;//row~n行第i列元素全为0
swap(c[row],c[k]);
for(int j=row+1;j<=n;j++)
if(c[j][i])
c[j]^=c[row];
row++;
}
return (n-row+1);
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&b[i][j]);
int cnt=0;
for(int C=1;C<=n;C++)//枚举当前处理的列
{
for(int i=1;i<=n;i++) B[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(j==i) c[i][j]=a[i][j]^b[i][C];
else c[i][j]=a[i][j];
cnt+=calc();//处理当前矩阵有多少*元
}
printf("%lld",qmi(2,cnt));
return 0;
}