CodeForces - 385E Bear in the Field —— 矩阵快速幂
题目链接:https://vjudge.net/problem/CodeForces-385E
1 second
256 megabytes
standard input
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.
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).
Print two integers — the coordinates of the cell the bear will end up in after t seconds.
5 1 2 0 1 2
3 1
1 1 1 -1 -1 2
1 1
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.
题解:
1.为了方便取模,把x、y轴都改成从0开始,最后加1即可。设(sx[t], sy[t])为t时刻的位置,(dx[t], dy[t])为从t-1到t时间段的速度(偏移量),根据题意,可得:
dx[t] = dx[t-1] + sx[t-1] +1 + sy[t-1]+1 + t-1
dy[t] = dy[t-1] + sx[t-1] +1 + sy[t-1]+1 + t-1
sx[t] = sx[t-1] + dx[t-1] + sx[t-1] +1 + sy[t-1]+1 + t-1
sy[t] = sy[t-1] + dy[t-1] + sx[t-1] +1 + sy[t-1]+1 + t-1
2.根据上述递推式,构造矩阵求解即可。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
//const int MOD = 1e9+7;
const int MAXN = 1e6+; int MOD;
const int Size = ;
struct MA
{
LL mat[Size][Size];
void init()
{
for(int i = ; i<Size; i++)
for(int j = ; j<Size; j++)
mat[i][j] = (i==j);
}
}; MA mul(MA x, MA y)
{
MA ret;
memset(ret.mat, , sizeof(ret.mat));
for(int i = ; i<Size; i++)
for(int j = ; j<Size; j++)
for(int k = ; k<Size; k++)
ret.mat[i][j] += (1LL*x.mat[i][k]*y.mat[k][j]%MOD+MOD)%MOD, ret.mat[i][j] %= MOD;
return ret;
} MA qpow(MA x, LL y)
{
MA s;
s.init();
while(y)
{
if(y&) s = mul(s, x);
x = mul(x, x);
y >>= ;
}
return s;
} MA tmp = {
,,,,,,
,,,,,,
,,,,,,
,,,,,,
,,,,,,
,,,,,
}; int main()
{
LL n, sx, sy, dx, dy, t;
while(scanf("%lld%lld%lld%lld%lld%lld",&n,&sx,&sy,&dx,&dy,&t)!=EOF)
{
MOD = n;
MA s = tmp;
s = qpow(s, t); sx--; sy--;
LL a[] = {dx,dy,sx,sy,,};
sx = sy = ;
for(int i = ; i<Size; i++)
{
sx += (1LL*s.mat[][i]*a[i]%MOD+MOD)%MOD, sx %= MOD;
sy += (1LL*s.mat[][i]*a[i]%MOD+MOD)%MOD, sy %= MOD;
}
printf("%lld %lld\n", sx+, sy+);
}
}
最新文章
- iOS网络4——Reachability检测网络状态
- django 模型
- iosOpenDev-install 失败官方wiki无法解决看这里(尝试有效)
- Cheatsheet: 2015 08.01 ~ 08.31
- MyEclipse下创建的项目导入到Eclipse中详细的图文配置方法
- 2016年6月28日 星期二 --出埃及记 Exodus 14:25
- [Yii][RBAC]Yii中应用RBAC完全指南
- Android之Intent
- Oracle start with connect by prior 用法
- java中文乱码解决之道(二)—–字符编码详解:基础知识 + ASCII + GB**
- Ubuntu在ARM上建立NFS服务
- 微信小程序框架探究和解析
- 如何配置VS使得可以通过域名或IP访问
- 原生js的一些研究和总结(1)
- Java开发笔记(四十五)成员属性与成员方法
- js循环出相同name,不同id的按钮,对其进行点击回复操作
- 【转】判断处理器是Big_endian的还是Little_endian的
- Java面试(一) -- 基础部分(1)
- 新巴巴运动网上商城 项目 快速搭建 教程 The new babar sports online mall project quickly builds a tutorial
- deepin系统安装成功了之后重启电脑没有deepin启动选项的简单解决办法