E. Bear in the Field
time limit per test 1 second
memory limit per test 256 megabytes
input standard input
output standard output
Our bear's forest has a checkered field. The checkered field is an n?×?n table, the rows are numbered from 1 to n from top to bottom, the columns are numbered from 1 to n from left to right. Let's denote a cell of the field on the intersection of row x and column y by record (x,?y). Each cell of the field contains growing raspberry, at that, the cell (x,?y) of the field contains x?+?y raspberry bushes.
The bear came out to walk across the field. At the beginning of the walk his speed is (dx,?dy). Then the bear spends exactly t seconds on the field. Each second the following takes place:
Let's suppose that at the current moment the bear is in cell (x,?y).
First the bear eats the raspberry from all the bushes he has in the current cell. After the bear eats the raspberry from k bushes, he increases each component of his speed by k. In other words, if before eating the k bushes of raspberry his speed was (dx,?dy), then after eating the berry his speed equals (dx?+?k,?dy?+?k).
Let's denote the current speed of the bear (dx,?dy) (it was increased after the previous step). Then the bear moves from cell (x,?y)to cell (((x?+?dx?-?1) mod n)?+?1,?((y?+?dy?-?1) mod n)?+?1).
Then one additional raspberry bush grows in each cell of the field.
You task is to predict the bear's actions. Find the cell he ends up in if he starts from cell (sx,?sy). Assume that each bush has infinitely much raspberry and the bear will never eat all of it.
Input
The first line of the input contains six space-separated integers: n, sx, sy, dx, dy, t(1?≤?n?≤?109; 1?≤?sx,?sy?≤?n; ?-?100?≤?dx,?dy?≤?100; 0?≤?t?≤?1018).
Output
Print two integers — the coordinates of the cell the bear will end up in after t seconds.
Examples
input
5 1 2 0 1 2
output
3 1
input
1 1 1 -1 -1 2
output
1 1
Note
Operation a mod b means taking the remainder after dividing a by b. Note that the result of the operation is always non-negative. For example, (?-?1) mod 3?=?2.
In the first sample before the first move the speed vector will equal (3,4) and the bear will get to cell (4,1). Before the second move the speed vector will equal (9,10) and he bear will get to cell (3,1). Don't forget that at the second move, the number of berry bushes increased by 1.
In the second sample before the first move the speed vector will equal (1,1) and the bear will get to cell (1,1). Before the second move, the speed vector will equal (4,4) and the bear will get to cell (1,1). Don't forget that at the second move, the number of berry bushes increased by 1.
题意：
n*n的方格上吃草莓，每个格子上的初始草莓数目为行列的坐标和（如（1,2）处的初始草莓=2），并且每过一秒所有格子上的草莓数目+1。有一只小熊的初始位置为(sx,sy),小熊的两个方向上的速度为(dx,dy)，当前格子上的草莓数为k*（注意：每个格子上的草莓数不会变小，也就是说第t秒时，(x,y)处的草莓数目为x+y+t），那么下一秒小熊的位置为(x+dx+k,y+dy+k)，小熊的速度为(dx+k,dy+k)。
题目小熊的初始位置（sx,sy），初始速度（dx,dy），时间t，求第t秒时小熊的位置。
思路：
我们设然后用矩阵快速幂求解
x[t+1] = x[t] + dx[t+1]
= 2 * x[t] + y[t]+dx[t]+0*dy[t]+ t[t]
y[t+1] = y[t] + dy[t+1]
= x[t] + 2 * y[t] +0*dx[t]+dy[t] + t[t]
dx[t+1] = x[t] + y[t]+dx[t] +0*dy[t] + t[t]
dy[t+1] = x[t] + y[t] +0*dx[t]+dy[t] + t[t]
t[t+1] = t[t] + 1
1 = 1（为了构造方阵）
所以，关系矩阵A
1,0,1,1,1,0,
0,1,1,1,1,0,
1,0,2,1,1,0,
0,1,1,2,1,0,
0,0,0,0,1,1,
0,0,0,0,0,1。
注意一下取mod和坐标从1开始就行
//矩阵快速幂注意特判
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define N 10005
using namespace std;
const int MAXN= 15;
typedef long long ll;
ll p;
int len=6;//构造矩阵的长度
struct Matrix//注意定义的是方阵，*法也是
{ll M[MAXN][MAXN];Matrix(const bool I = 0) ///初始化对角矩阵{memset(M, 0, sizeof(M));if (I)for(int i = 0; i < len; i++) M[i][i] = 1;}Matrix operator *(const Matrix &y) ///矩阵乘法，对乘法重新定义，z=x*y{Matrix z;for (int i = 0; i < len; i++)//x矩阵的nfor (int j = 0; j < len; j++)//y矩阵的nfor (int k = 0; k < len; k++)//xy矩阵的mz.M[i][j] = (z.M[i][j]+M[i][k]*y.M[k][j])%p;return z;}void out(){for (int i = 0; i < len; i++){for (int j = 0; j < len; j++)cout << M[i][j] << " ";cout << "\n";}}
};Matrix Pow(Matrix A, ll b)///矩阵的快速幂
{Matrix ans = Matrix(1);for (;b; b>>=1){if(b&1) ans=ans*A;A = A*A;}return ans;
}
ll temp[6][6] = {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};
int main()
{ len=6; ///构造矩阵的长度ll n,sx,sy,dx,dy,t;while(scanf("%lld%lld%lld%lld%lld%lld",&n,&sx,&sy,&dx,&dy,&t)!=-1){p=n;if(t==0)printf("%lld %lld\n",sx,sy);else{Matrix a;for(int i=0;i<len;i++)for(int j=0;j<len;j++){a.M[i][j]=temp[i][j];}a=Pow(a,t);//a.out();t=0;sx--;sy--;dx=(dx%p+p)%p;dy=(dy%p+p)%p;Matrix b;b.M[0][0]=sx;b.M[1][0]=sy;b.M[2][0]=dx;b.M[3][0]=dy;b.M[4][0]=0;b.M[5][0]=1;b=a*b;//b.out();printf("%lld %lld\n",b.M[0][0]+1,b.M[1][0]+1); }}return 0;
}