2021年儿童节J 智乃酱的配电箱谜题
智乃酱的配电箱谜题
https://ac.nowcoder.com/acm/contest/16489/J
这是一道线性代数经典题，问题来了，为什么儿童节要做线性代数呢。
阿巴阿巴阿巴，我也不知道，可能我就是想出个数学题吧。（线性代数和数奥也差不多不是）
首先肯定可以想到k很小，可以矩阵建图。考虑每一层网络之间的图都建成一个矩阵。
例如第一层网络到第二层网络。如果第i个开关链接下层的第j个接线柱，矩阵的第i行第j列就是1，反之就是0。
例如样例中的上层网络就是
这时候继续看样例，如果数理基础好的话其实立刻就反应过来了，为啥呢，因为样例中下层网络直接连上去的，不起任何作用。
我们要构造答案的中层网络为
然后进一步发现
它们做矩阵乘的结果是单位元e。它会是某种巧合么？当然不可能是什么巧合啊。这个题讲到这里估计有线代基础的同学就已经会了。
ok，现在回到问题本身，对于某一层矩阵，当我们定义矩阵的第i行第j列为第i个接线柱是否控制接下层的第j个接线柱。控制为1，不控制为0时。
考虑两层网络的影响如何合并，即假设现在有两张用矩阵建的图，第一个矩阵A表示第一层中第i行第k列为第i个接线柱是否控制接第二层的第k个接线柱。第二个矩阵B表示第二层中第k行第j列为第k个接线柱是否控制接第三层的第j个接线柱。
现在如果我问，第一层的第i个接线柱是否对第三场第j个接线柱有控制关系，记这个关系为，如何用数学公式表示？
你会发现合并两层控制网络这个操作的代数意义恰好是模二意义下的矩阵乘。
设上层网络为矩阵A，中间层网络为矩阵x，下层网络为矩阵B。
最终达到的效果“第i开关仅控制第i个灯泡”，为矩阵乘法单位元e。
则有方程式。
利用逆元移项
得
。
也就是说本题只要求上下两层网络矩阵的逆矩阵，再做模二意义下的乘法即可。
最后再遍历邻接矩阵输出中层网络图。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
int A[MAXN][MAXN<<1];
struct mat
{
int row;
int col;
int a[MAXN][MAXN];
mat(int n=0,int m=0,long long p=0)
{
row=n;
col=m;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
a[i][j]=0;
}
}
for(int i=1;i<=n;++i)
{
a[i][i]=p;
}
}
void row_minus(int a,int b)
{
for(int i=1;i<=2*row;++i)
{
A[a][i]^=A[b][i];
}
return;
}
void row_swap(int a,int b)
{
for(int i=1;i<=2*row;++i)
{
swap(A[a][i],A[b][i]);
}
}
mat inv()
{
memset(A,0,sizeof(A));
for(int i=1;i<=row;++i)
{
for(int j=1;j<=row;++j)
{
A[i][j]=a[i][j];
A[i][row+j]=i==j;
}
}
for(int i=1;i<=row;++i)
{
if(!A[i][i])
{
for(int j=i+1;j<=row;++j)
{
if(A[j][i])
{
row_swap(i,j);
break;
}
}
}
assert(A[i][i]);
for(int j=i+1;j<=row;++j)
{
if(A[j][i])
{
row_minus(j,i);
}
}
}
for(int i=row;i;--i)
{
for(int j=i-1;j;--j)
{
if(A[j][i])
{
row_minus(j,i);
}
}
}
mat ret(row,row);
for(int i=1;i<=row;++i)
{
for(int j=1;j<=row;++j)
{
ret.a[i][j]=A[i][row+j];
}
}
return ret;
}
int count()
{
int ret=0;
for(int i=1;i<=row;++i)
{
for(int j=1;j<=col;++j)
{
ret+=a[i][j];
}
}
return ret;
}
};
mat operator *(const mat &x,const mat &y)
{
mat ans;
for(int i=1;i<=x.row;++i)
{
for(int j=1;j<=y.col;++j)
{
ans.a[i][j]=0;
for(int k=1;k<=x.col;++k)
{
ans.a[i][j]^=x.a[i][k]&y.a[k][j];
}
}
}
ans.row=x.row;
ans.col=y.col;
return ans;
}
void operator *=(mat &x,mat y)
{
x=x*y;
}
int n,m,k,u,v;
mat a,b,c;
int main()
{
scanf("%d %d %d",&n,&m,&k);
a.row=a.col=b.row=b.col=k;
for(int i=1;i<=n;++i)
{
scanf("%d %d",&u,&v);
a.a[u][v]=1;
}
for(int i=1;i<=m;++i)
{
scanf("%d %d",&u,&v);
b.a[u][v]=1;
}
c=a.inv()*b.inv();
printf("%d\n",c.count());
for(int i=1;i<=c.row;++i)
{
for(int j=1;j<=c.col;++j)
{
if(c.a[i][j])
{
printf("%d %d\n",i,j);
}
}
}
return 0;
} 
投递蔚来等公司10个岗位
