Bear in the Field
题目链接
分类：math matrices
1.题意概述
有一片
n×n
的草莓地，每个位置的初始草莓量为横坐标和纵坐标的和，然后每过一秒增长一个草莓。然后给出熊的初始位置
(sx,sy)
，以及移动的速度
(dx,dy)
，每一秒发生的事：
速度增加
k
（
k为该位置的草莓数）熊的位置发生移动每个位置上草莓数
+1
2.解题思路
容易推出的转移方程是：
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪sx[t]=sx[t−1]+dx[t−1]+sx[t−1]+sy[t−1]+t−1+2sy[t]=sy[t−1]+dy[t−1]+sx[t−1]+sy[t−1]+t−1+2dx[t]=dx[t−1]+sx[t−1]+sy[t−1]+t−1+2dy[t]=dy[t−1]+sx[t−1]+sy[t−1]+t−1+2t=t−1+1
但是看数据范围：
1 ≤n≤ 109;1 ≤sx, sy≤ n; − 100 ≤ dx, dy ≤ 100;0 ≤ t ≤ 1018
正常的转移时间复杂度
O(t)
是很难接受的，根据递推的线性，我们可以考虑构造矩阵加速转移过程：
⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢sx[t]sy[t]dx[t]dy[t]t1⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢211100121100101000010100111110222211⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥×⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢sx[t−1]sy[t−1]dx[t−1]dy[t−1]t−11⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥
3.AC代码
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define e exp(1.0)
#define pi acos(-1.0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
#define INF 0x3f3f3f3f
#define maxn 100010
#define N 7
typedef vector<int> VI;
typedef pair<
int,
int> PII;
typedef long long ll;
typedef unsigned long long ull;
ll mod =
1e9 +
7;
class Matrix {
public:
ll a[N][N];
int n;
void Init(
int key) {
memset(a,
0,
sizeof a);
if (key)
rep(i,
0, n) a[i][i] =
1;
}
Matrix
operator+ (
const Matrix &b) {
Matrix c;
c.n = n;
rep(i,
0, n) rep(j,
0, n) c.a[i][j] = (a[i][j] + b.a[i][j]) % mod;
return c;
}
Matrix
operator+ (
int x) {
Matrix p = *
this;
rep(i,
0, n) p.a[i][i] = (p.a[i][i] + x % mod) % mod;
return p;
}
Matrix
operator- (
const Matrix &b) {
Matrix c;
c.n = n;
rep(i,
0, n) rep(j,
0, n) c.a[i][j] = (a[i][j] - b.a[i][j] + mod) % mod;
return c;
}
Matrix
operator* (
const Matrix &b) {
Matrix c;
c.n = n;
c.Init(
0);
rep(i,
0, n) rep(j,
0, n) rep(k,
0, n)
c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod + mod) % mod;
return c;
}
Matrix Power(ll t) {
Matrix ans, p = *
this;
ans.n = p.n;
ans.Init(
1);
while (t) {
if (t &
1) ans = ans * p;
p = p * p;
t >>=
1;
}
return ans;
}
void Print() {
rep(i,
0, n) {
rep(j,
0, n) {
if (j ==
0)
printf(
"%I64d", a[i][j]);
else printf(
" %I64d", a[i][j]);
}
puts(
"");
}
}
};
int main() {
#ifndef ONLINE_JUDGE
freopen(
"in.txt",
"r", stdin);
freopen(
"out.txt",
"w", stdout);
long _begin_time = clock();
#endif
Matrix A, f;
ll n, sx, sy, dx, dy, t;
scanf(
"%I64d%I64d%I64d%I64d%I64d%I64d", &n, &sx, &sy, &dx, &dy, &t);
mod = n;
f.Init(
0); f.n =
6;
f.a[
0][
0] = f.a[
0][
5] = f.a[
1][
1] = f.a[
1][
5] = f.a[
2][
5] = f.a[
3][
5] =
2;
f.a[
0][
1] = f.a[
0][
2] = f.a[
0][
4] = f.a[
1][
0] = f.a[
1][
3] = f.a[
1][
4] = f.a[
2][
0] = f.a[
2][
1] = f.a[
2][
2] = f.a[
2][
4] =
1;
f.a[
3][
0] = f.a[
3][
1] = f.a[
3][
3] = f.a[
3][
4] = f.a[
4][
4] = f.a[
4][
5] = f.a[
5][
5] =
1;
A.Init(
0); A.n =
6;
A.a[
0][
0] = sx -
1;
A.a[
1][
0] = sy -
1;
A.a[
2][
0] = dx;
A.a[
3][
0] = dy;
A.a[
4][
0] =
0;
A.a[
5][
0] =
1;
A = f.Power(t) * A;
printf(
"%I64d %I64d\n", A.a[
0][
0] +
1, A.a[
1][
0] +
1);
#ifndef ONLINE_JUDGE
long _end_time = clock();
printf(
"time = %ld ms.", _end_time - _begin_time);
#endif
return 0;
}
