[THUPC 2023 决赛] Freshman Dream

· · 题解

更好的阅读体验

感谢 Cczzyy20150005 大佬指出了矩阵化简的错误。

题目大意

给定 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})\cdot B_{1,k}]\oplus [A_{1,2}\cdot B_{2,k}]\oplus \cdots \oplus [A_{1,n}\cdot B_{n,k}]=0 \\ [A_{2,1}\cdot B_{1,k}]\oplus [(A_{2,2}\oplus A_{2,k})\cdot B_{2,k}]\oplus \cdots \oplus [A_{2,n}\cdot B_{n,k}]=0 \\ \vdots \\ [A_{n,1}\cdot B_{1,k}]\oplus [A_{n,2}\cdot B_{2,k}]\oplus \cdots \oplus [(A_{n,n}\oplus A_{n,k})\cdot 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;
}