【THUPC 2023 决赛】 Freshman Dream

· 2024-07-11 · # 线性代数 # 题解

题目大意

给定 $n\times n$ 的 $01$ 矩阵 $A$ 要求构造同样大小的矩阵 $B$ 要求满足 $A\times B$ 与两个矩阵中的元素一一乘起来，而且要求 $B$ 矩阵中恰好有 $k$ 个 $1$ 。

数据范围满足 $1\le n\le 100,0\le k\le n^2$ 且 $A$ 为随机生成。

思路

分析矩阵乘法的定义 $(A\times B)_{i,j}=\sum\limits_{k=1}^n A_{i,k}\cdot b_{k,j}$ ，可以发现对于 $B$ 矩阵的第 $j$ 行是相对独立的可以单独讨论。

分析题目条件，先不考虑取模，可以列出方程：

\left\{\begin{matrix} A_{1,1}\cdot B_{1,k}+A_{1,2}\cdot B_{2,k}+\cdots +A_{1,n}\cdot B_{n,k}=A_{1,k}\cdot B_{1,k} \\ A_{2,1}\cdot B_{1,k}+A_{2,2}\cdot B_{2,k}+\cdots +A_{2,n}\cdot B_{n,k}=A_{2,k}\cdot B_{2,k} \\ \vdots \\ A_{n,1}\cdot B_{1,k}+A_{n,2}\cdot B_{2,k}+\cdots +A_{n,n}\cdot B_{n,k}=A_{n,k}\cdot B_{n,k} \end{matrix}\right.

接着进行移项：

\left\{\begin{matrix} A_{1,1}\cdot B_{1,k}+A_{1,2}\cdot B_{2,k}+\cdots +A_{1,n}\cdot B_{n,k}-A_{1,k}\cdot B_{1,k}=0 \\ A_{2,1}\cdot B_{1,k}+A_{2,2}\cdot B_{2,k}+\cdots +A_{2,n}\cdot B_{n,k}-A_{2,k}\cdot B_{2,k} =0 \\ \vdots \\ A_{n,1}\cdot B_{1,k}+A_{n,2}\cdot B_{2,k}+\cdots +A_{n,n}\cdot B_{n,k}-A_{n,k}\cdot B_{n,k}=0 \end{matrix}\right.

提取公因式：

\left\{\begin{matrix} (A_{1,1}-A_{1,k})\cdot B_{1,k}+A_{1,2}\cdot B_{2,k}+\cdots +A_{1,n}\cdot B_{n,k}=0 \\ A_{2,1}\cdot B_{1,k}+(A_{2,2}-A_{2,k})\cdot B_{2,k}+\cdots +A_{2,n}\cdot B_{n,k}=0 \\ \vdots \\ A_{n,1}\cdot B_{1,k}+A_{n,2}\cdot B_{2,k}+\cdots +(A_{n,n}-A_{n,k})\cdot B_{n,k}=0 \end{matrix}\right.

考虑因为所有的元素都是 $0$ 或者 $1$ ，所以可以可以将上面的运算转化为异或。

\left\{\begin{matrix} (A_{1,1}\oplus A_{1,k})\oplus B_{1,k}\oplus A_{1,2}\oplus B_{2,k}\oplus \cdots \oplus A_{1,n}\oplus B_{n,k}=0 \\ A_{2,1}\oplus B_{1,k}\oplus (A_{2,2}\oplus A_{2,k})\oplus B_{2,k}\oplus \cdots \oplus A_{2,n}\oplus B_{n,k}=0 \\ \vdots \\ A_{n,1}\oplus B_{1,k}\oplus A_{n,2}\oplus B_{2,k}\oplus \cdots \oplus (A_{n,n}\oplus A_{n,k})\oplus B_{n,k}=0 \end{matrix}\right.

整理成系数的增广矩阵：

\begin{bmatrix} A_{1,1}\oplus A_{1,k} & A_{1,2} & \cdots & A_{1,n} &0 \\ A_{2,1} & A_{2,2}\oplus A_{2,k} & \cdots & A_{2,n} & 0\\ \vdots &\vdots &\ddots &\vdots &\vdots\\ A_{n,1} & A_{n,2} & \cdots & A_{n,n}\oplus A_{n,k} &0 \end{bmatrix}

写一个线性基（高斯消元也可以）求出方程的解，接着跑一个 DP 求出具体的方案即可。

其中 $f_{i,j}$ 表示是否有前 $i$ 行一共用了 $j$ 个 $1$ 的方案，而 $g_{i,j}$ 则记录了选择的方案。

总共的时间复杂度为 $O(n^4)$ ，但是有一个 bitset 的优化。

#include<iostream>
#include<bitset>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;
const int N=105;
int n,m,top;
bitset<N>A[N],a[N],s[N],g[N][N*N];
bitset<N*N>f[N];
vector<bitset<N> >st;
bool vis[N],ans[N][N];
int read(){int x;cin>>x;return x;}
void insert(bitset<N>a){
	for(int i=1;i<=n;i++){
		if(!a[i]) continue;
		if(s[i].none()){s[i]=a;return;}
		a^=s[i];
	}
}
void solve(int id){
	for(int i=1;i<=n;i++) a[i]=A[i],a[i][i]=A[i][i]^A[i][id],s[i].reset();
	for(int i=1;i<=n;i++) insert(a[i]);
	st.clear();
	for(int i=n;i>=1;i--){
		if(s[i].none()) continue;
		for(int j=1;j<i;j++) if(s[j][i]) s[j]^=s[i];
	}
	for(int i=1;i<=n;i++){
		if(!s[i].none()) continue;
		bitset<N> top;top[i]=1;
		for(int j=1;j<=n;j++) if(s[j][i]) top[j]=1;
        st.push_back(top);
	}
    memset(vis,0,sizeof(vis));
	for(int xwd=0;xwd<(1<<st.size());xwd++){
		bitset<N>top;
		for(int i=0;i<st.size();i++) if(xwd&(1<<i)) top^=st[i];
		int siz=top.count();
		if(vis[siz]) continue;
		vis[siz]=1;
		for(int i=siz;i<=m;i++) if(!f[id][i]&&f[id-1][i-siz]) f[id][i]=1,g[id][i]=top;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) A[i][j]=read();
	f[0][0]=1;
	for(int i=1;i<=n;i++) solve(i);
	if(!f[n][m]) cout<<-1<<'\n',exit(0);
	cout<<1<<'\n';
	for(int i=n,p=m;i>=1;i--){
		bitset<N> top=g[i][p];
		for(int j=1;j<=n;j++) if(top[j]) ans[j][i]=1;
		p-=top.count();
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cout<<ans[i][j]<<' ';
		cout<<'\n';
	}
	return 0;
}