本文主要是介绍Codeforces 385E Bear in the Field(矩阵快速幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：Codeforces 385E Bear in the Field
题目大意：有一片n*n的草莓地，每个位置的初始草莓量为横坐标和纵坐标的和，然后每过一秒增长一个草莓。然后给出熊的初始位置（sx，sy），以及移动的速度（dx，dy），每一秒发生的事：（1）速度增加k（k为该位置的草莓数）;（2)熊的位置发生移动；（3）每个位置上草莓数+1
解题思路：矩阵快速幂，根据题目给出的条件,先让坐标从0~n-1.然后输出时+1即可。
sx[t] = sx[t-1] + dx[t-1] + k = sx[t-1] + dx[t-1] + sx[t-1] + sy[t-1] + t-1 + 2（因为坐标为0~n-1）
sy[t] = sy[t-1] + dy[t-1] + k = sy[t-1] + dy[t-1] + sx[t-1] + sy[t-1] + t-1 + 2
dx[t] = dx[t-1] + sx[t-1] + sy[t-1] + t-1 + 2
dy[t] = dy[t-1] + sx[t-1] + sy[t-1] + t-1 + 2
t = t-1 + 1
所以就可以写出矩阵
2 1 1 0 1 2
1 2 0 1 1 2
1 1 1 0 1 2
1 1 0 1 1 2
0 0 0 0 1 1
0 0 0 0 0 1
#include <stdio.h>
#include <string.h>
#include <iostream>using namespace std;typedef long long ll;
const int N = 10;ll n, sx, sy, dx, dy, t;struct mat {int r, c;ll k[N][N];void init(int r, int c) {this->r = r; this->c = c;memset(k, 0, sizeof(k));}void clear() {//memset(k, 0, sizeof(k));k[0][0] = k[0][5] = k[1][1] = k[1][5] = k[2][5] = k[3][5] = 2;k[0][1] = k[0][2] = k[0][4] = k[1][0] = k[1][3] = k[1][4] = k[2][0] = k[2][1] = k[2][2] = k[2][4] = 1;k[3][0] = k[3][1] = k[3][3] = k[3][4] = k[4][4] = k[4][5] = k[5][5] = 1;}friend mat operator * (const mat& a, const mat& b) {mat ans;ans.init(a.r, b.c);for (int i = 0; i < ans.r; i++) {for (int j = 0; j < ans.c; j++) {for (int x = 0; x < b.r; x++)ans.k[i][j] = ((ans.k[i][j] + a.k[i][x] * b.k[x][j]) % n + n) % n;}}return ans;}
};int main() {cin >> n >> sx >> sy >> dx >> dy >> t;mat ans;ans.init(6, 1);ans.k[0][0] = sx - 1;ans.k[1][0] = sy - 1;ans.k[2][0] = dx;ans.k[3][0] = dy;ans.k[4][0] = 0;ans.k[5][0] = 1;mat b;b.init(6, 6);b.clear();while (t) {if (t&1)ans = b * ans;b = b * b;t>>=1;}cout << ans.k[0][0] + 1 << " " << ans.k[1][0] + 1 << endl;return 0;
}
这篇关于Codeforces 385E Bear in the Field(矩阵快速幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
