左乘只需要把 A 中 $(i, j)$ 位置赋值到 $(j, i)$ 就变成了我们习惯的右乘。

此题就是要一种较快的算矩阵快速幂的方法。

正解大概是用一种 复杂度较优的矩阵乘法，但是这个东西好像很难写。

各种优化方法：

• 预处理 $2^k$ 的矩阵。
• bitset 优化。看矩阵乘法的那个形式，$A = B \times C$，$A(i, j)$ 位置的贡献相当于 $B$ 的第 $i$ 行和 $C$ 的第 $j$ 列按位与起来，然后答案是 $1$ 的个数的奇偶性，这个瓶颈我只会近似带 $5$ 倍常数 $O(1)$ 求，求大佬指点更优复杂度做法（。
• 手写 bitset（实测 uint 比 unsigned long long 快
• 开火车头

这样复杂度大概是 $O(\frac{m^3}{w}\log k + n\frac{m^2}{w} \log k)$

是个 $10^9$ 计算量级的东西。。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse-lm")

#include <iostream>
#include <cstdio>
#include <bitset>
#include <cstring>
#define rint register int
using namespace std;

typedef unsigned int U;

const int N = 1000, W = 32;


inline int cb(U x){  
    x = x ^ (x >> 1);
    x = x ^ (x >> 2);
    x = x ^ (x >> 4);
    x = x ^ (x >> 8);
    x = x ^ (x >> 16);
    return x;
}

struct Bit{
    U a[32];
    void inline set1(int x) {
        a[x >> 5] |= 1ull << (x & 31);
    }
    void inline set0(int x) {
        a[x >> 5] &= ~(1ull << (x & 31));
    }
    int inline get(int x) {
        return a[x >> 5] >> (x & 31) & 1;
    }
    void inline clear() {
        memset(a, 0, sizeof a);
    }
    Bit operator & (const Bit &b) const {
        Bit c;
        for (rint i = 0; i < 32; i++)
            c.a[i] = a[i] & b.a[i];
        return c;
    }
    bool inline count() {
        int res = 0;
        for (rint i = 0; i < 32; i++)
            res ^= cb(a[i]);
        return res & 1;
    }   
};

struct Mat{
    Bit w[N], bw[N];
    int n, m;
    Mat inline operator * (const Mat &b) const {
        Mat c; c.n = n, c.m = b.m;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c.m; j++) {
                if ((w[i] & b.bw[j]).count()) 
                    c.w[i].set1(j), c.bw[j].set1(i);
                else c.w[i].set0(j), c.bw[j].set0(i);
            }
        }
        return c;
    }
} s, A[30];

int m;

char str[N + 5];

int main() {
    scanf("%d", &m);
    A[0].n = A[0].m = m, s.n = 1, s.m = m;
    for (int i = 0; i < m; i++) {
        scanf("%s", str);
        for (int j = 0; j < m; j++) {
            if (str[j] == '1') A[0].w[j].set1(i), A[0].bw[i].set1(j);
        }
    }
    scanf("%s", str);
    for (int i = 0; i < m; i++) {
        if (str[i] == '1') s.w[0].set1(i), s.bw[i].set1(0);
    }
    for (int i = 1; i < 30; i++) A[i] = A[i - 1] * A[i - 1];
    int n; scanf("%d", &n);
    while (n--) {
        int b; scanf("%d", &b);
        Mat res = s;
        for (int i = 0; i < 30; i++) {
            if (b >> i & 1) res = res * A[i]; 
        }
        for (int i = 0; i < m; i++) putchar(res.w[0].get(i) ? '1' : '0');
        puts("");
    }
}