# 题意

• $1 \leq T \leq 20$
• $0 \leq A, B, C, D \leq 10^9$
• $1 \leq P, n \leq 10^9$

# 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modulo = (ll) 1e9 + 7;

class matrix{
public:
ll s[3][3];

matrix(){
memset(s, 0, sizeof(s));
}
matrix(ll Fn, ll Fn1, ll E) {
s[0][0] = Fn;
s[0][1] = Fn1;
s[0][2] = E;
s[1][0] = s[1][1] = s[1][2] = 0;
s[2][0] = s[2][1] = s[2][2] = 0;
}
matrix(ll C, ll D) {
s[0][0] = D;
s[1][0] = C;
s[0][1] = s[2][0] = s[2][2] = 1;
s[0][2] = s[1][1] = s[1][2] = s[2][1] = 0;
}
};

matrix mul(matrix &a, matrix &b) {
matrix ret;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
ret.s[i][j] = (ret.s[i][j] + a.s[i][k] * b.s[k][j]) % modulo;
}
}
}
return ret;
}

ll A = 0, B = 0, C = 0, D = 0, P = 0, n = 0;

void xmul(ll &Fn, ll &Fn1, ll E, ll t) {
matrix ret(Fn, Fn1, E);
matrix b(C, D);
while (t) {
if (t & 1) {
ret = mul(ret, b);
}
b = mul(b, b);
t >>= 1;
}
Fn = ret.s[0][0];
Fn1 = ret.s[0][1];
}

ll solve() {
if (n == 1) return A;
if (n == 2) return B;
ll Fn1 = A, Fn = B, nex = 0, PN = 0;
matrix res;
for (ll i = 3; i <= n; ) {
PN = P / i;
if (PN == 0) {
nex = n;
} else {
nex = min(n, P / PN);
}
xmul(Fn, Fn1, PN, nex - i + 1);
i = nex + 1;
}
return Fn;
}

int main() {
int T = 0;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld%lld%lld%lld", &A, &B, &C, &D, &P, &n);
printf("%lld\n", solve());
}
}

# 题意

• $2 \le N, M \le 2048$
• $1 \le P \le 64$
• $0 \le A_{ij} \le 65536$

# 思路

STFW看看有没有什么快速算矩阵的方法，没有

# 代码

#include <bits/stdc++.h>
using namespace std;

int n = 0, p = 0, m = 0, bk = 0;
int a[4200][70] = {};
int b[4200][70] = {};
int c[4200][4200] = {};
int apre[4200][10][260] = {};
int bpre[4200][10] = {};
char s[100] = {};

void pre() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < bk; ++j) {
for (int k = 0; k < 256; ++k) {
for (int p = 0; p < 8; ++p) {
if ((k >> p) & 1) {
apre[i][j][k] += a[i][(j << 3) + p];
}
}
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < bk; ++j) {
for (int p = 0; p < 8; ++p) {
bpre[i][j] += b[i][(j << 3) + p] << p;
}
}
}
}

int getAns() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int p = 0; p < bk; ++p) {
c[i][j] += apre[i][p][bpre[j][p]];
}
}
}

int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j= 0; j < m; ++j) {
ans ^= c[i][j];
}
}
return ans;
}

int main() {
scanf("%d%d%d", &n, &p, &m), bk = ((p - 1) >> 3) + 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < p; ++j) {
scanf("%x", &a[i][j]);
}
}
for (int i = 0; i < m; ++i) {
scanf("%s", s);
for (int j = 0; j < p; ++j) {
b[i][j] = s[j] - '0';
}
}
pre();
printf("%d\n", getAns());
return 0;
}