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(矩阵快速幂）

原文：http://blog.csdn.net/keshuai19940722/article/details/18867095