题解 P3890 【[GDOI2014]比特矩阵】

· · 题解

由于我太菜，不会证明和更优的做法，只能打简单的暴力。

通过暴力模拟计算过程，可以发现这题定义的矩阵乘法并不满足结合律，不能使用矩阵快速幂，要寻找其他办法。

数据范围中的 m 很大，所以可以考虑是否存在一定规律可以缩小 m 的范围，再利用暴力计算。
通过小数据打表发现题中运算有循环节，且循环节很小（以 2 为循环节可以拿到很高分数），所以可以暴力计算找循环节，找到 m 在对应位置的答案即可。
代码不是很难，如果发现规律题目就比较简单了。

我的代码中用 map 来判断循环节，需要定义一个矩阵间的比较，否则会报错。

#include <bits/stdc++.h>
using namespace std;
int n, m;
struct Matrix {
    int x[502][502];
} A, ans;
inline void print(const Matrix &a) {
    for (register int i = 1; i <= n; ++i) {
        for (register int j = 1; j <= n; ++j) {
            printf("%d ", a.x[i][j]);
        }
        puts("");
    }
    return;
}
//map 用的比较，能判出不同就可以
inline bool operator<(const Matrix &a, const Matrix &b) {
    for (register int i = 1; i <= n; ++i) {
        for (register int j = 1; j <= n; ++j) {
            if (a.x[i][j] != b.x[i][j]) {
                return a.x[i][j] < b.x[i][j];
            }
        }
    }
    return false;
}
//下面是根据题意写的暴力矩阵乘法
inline Matrix mult(const Matrix &a, const Matrix &b) {
    Matrix C;
    memset(C.x, 0, sizeof(C.x));
    for (register int k = 1; k <= n; ++k) {
        for (register int i = 1; i <= n; ++i) {
            for (register int j = 1; j <= n; ++j) {
                C.x[i][j] |= (a.x[i][k] ^ b.x[k][j]);
            }
        }
    }
    return C;
}
namespace solve {
    map<Matrix, int> mp;  //判循环节
    //key->矩阵，val->编号
    Matrix fmp[10];  //存储上面 map 里对应编号的矩阵
    //key->编号，val->矩阵
    void work() {
        mp.clear();  memset(fmp, 0, sizeof(fmp));
        mp[ans] = 1;
        fmp[1] = ans;
        for (int i = 2; i <= m; ++i) {
            ans = mult(ans, A);
            if (mp.count(ans)) {//出现过，找到了循环节
                int xx = mp[ans];
                m = (m - xx) % (i - xx) + xx;
                //将 m 缩小找到对应矩阵
                ans = fmp[m];
                break;
            } else {
                mp[ans] = i;
                fmp[i] = ans;
            }
        }
        print(ans);
        return;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= n; ++i) {
        for (register int j = 1; j <= n; ++j) {
            scanf("%d", &A.x[i][j]);
        }
    }
    ans = A;
    solve::work();
    return 0;
}