Cydiater

「雅礼集训 2017 Day5」矩阵

给定大小为$n$的$0/1$矩阵$C$,求有多少对$n$阶$0/1$矩阵$A,B$,满足$A \times B = C$,对$10^9+ 7$取模后输出。

首先考虑$A \times B = C$,$A, C$分别看做$n$个长度为$n$的向量,那么$C$实际上是$A$每个向量的线性组合。容易发现,对于任意的矩阵$A,C$来说,当且仅当$C$的所有向量处在$A$的线性空间中,才存在矩阵$B$使得$A \times B = C$,而且若矩阵$A$的秩为$m$,那么恰好有$(2^{n - m})^n$种合法的$B$。

继续观察,可以发现对于所有秩相同的$C$来说,合法的$A,B$数量是相同的。那么实际有用的状态就只是矩阵的秩的大小。令$C$的秩为$r$,考虑设计 DP 。

我们设$f(i,j)$表示对于$i \times n$的$0/1$矩阵来说,秩为$j$的矩阵有$f(i,j)$个,可以在$O(n ^ 2)$的时间内处理出来。

我们要得到$A\times B = C$中$C$的秩为$r$的方案数,显然其为$ans = \sum f(n, i)\times f(i, r) \times (2^{n - i})^n$。

最后我们把$ans$乘上$f(n, r)$的逆元即可。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int mod = 1e9 + 7;
const int MAXN = 2e3 + 5;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

int N, a[MAXN][MAXN], f[MAXN][MAXN], pw[MAXN];
bool ok[MAXN];

int main(){
    scanf("%d", &N);
    pw[0] = 1;
    up (i, 1, N) pw[i] = add(pw[i - 1], pw[i - 1]);
    up (i, 1, N) up (j, 1, N) scanf("%d", &a[i][j]);
    up (i, 1, N) {
        up (j, 1, N) if (!ok[j] && a[j][i]) {
            up (k, i, N) swap(a[i][k], a[j][k]);
            break;
        }
        if (!a[i][i]) continue;
        ok[i] = 1;
        up (j, 1, N) if (i != j && a[j][i]) 
            up (k, i, N) a[j][k] ^= a[i][k];
    }
    int r = 0;
    up (i, 1, N) r += a[i][i];
    f[0][0] = 1;
    up (i, 1, N) up (j, 0, i) {
        if (j) cadd(f[i][j], mul(f[i - 1][j - 1], pop(pw[N], pw[j - 1])));        
        cadd(f[i][j], mul(f[i - 1][j], pw[j]));
    }
    int ans = 0;
    up (i, r, N) cadd(ans, mul(mul(f[N][i], f[i][r]), qpow(pw[N - i], N)));
    cmul(ans, qpow(f[N][r], mod - 2));
    printf("%d\n", ans);
    return 0;
}