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

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

问题链接:https://vjudge.net/problem/CodeForces-385E

Solution:

注意到t很大,直接模拟会超时。

注意到x和y相关【二者共同决定速度的增量】,时间影响对速度也有影响【每一秒都会为每个单元贡献一个生长,从而影响熊的速度增量】,同时注意到,熊不会吃光每个树丛上的草莓【所以速度增量与是否走过当前方格无关】。

接着,发现总可以由上一个状态的x, y, dx, dy, t推出当前状态的对应值,并且推导方式固定,所以可以使用矩阵快速幂将复杂度降到\(O(6^3logt)\)。

注意到坐标范围1到n,取模的形式很麻烦,我们对原始坐标减1进行一次映射,新的坐标按照原来的顺序落在了0到n-1。

#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;
}