## 【CodeForces-385E】Bear in the Field【矩阵快速幂】

【CodeForces-385E】Bear in the Field【矩阵快速幂】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;

const int SIZE = 6;
LL n, sx, sy, dx, dy, t;
struct Matrix {
LL v[SIZE][SIZE];
Matrix operator * (const Matrix &m) const {
Matrix ret = {0};
for (int i = 0; i < SIZE; i++) {
for (int k = 0; k < SIZE; k++) {
if (v[i][k]) {
for (int j = 0; j < SIZE; j++) {
ret.v[i][j] = ((ret.v[i][j] + v[i][k] * m.v[k][j] % n) + n) % n;
}
}
}
}
return ret;
}
};

Matrix powMod(LL p, Matrix base) {
Matrix ret = {0};
ret.v[0][0] = sx - 1, ret.v[1][0] = sy - 1;
ret.v[2][0] = dx, ret.v[3][0] = dy;
ret.v[4][0] = 1, ret.v[5][0] = 0;
while (p) {
if (p & 1) ret = base * ret;
p >>= 1;
if (p) base = base * base;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
// cin.tie(NULL);
cin >> n >> sx >> sy >> dx >> dy >> t;
Matrix base = {0};
base.v[0][0] = base.v[0][4] = 2;
base.v[0][1] = base.v[0][2] = base.v[0][5] = 1;
base.v[1][1] = base.v[1][4] = 2;
base.v[1][0] = base.v[1][3] = base.v[1][5] = 1;
base.v[2][0] = base.v[2][1] = base.v[2][2] = base.v[2][5] = 1;
base.v[3][0] = base.v[3][1] = base.v[3][3] = base.v[3][5] = 1;
base.v[2][4] = base.v[3][4] = 2;
base.v[4][4] = 1;
base.v[5][4] = base.v[5][5] = 1;
base = powMod(t, base);
cout << base.v[0][0] + 1 << " " << base.v[1][0] + 1 << "\n";
return 0;
}