Codeforces Round #226 (Div. 2) E(矩阵快速幂)

约定不等于承诺〃 2022-06-06 10:54 149阅读 0赞

问题描述:

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 xand 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 tseconds.

Example

Input

5 1 2 0 1 2

Output

3 1

Input

1 1 1 -1 -1 2

Output

1 1

题目题意:题目给了我们一个n\*n的图，每个点上有x+y个草莓，熊从sx,sy出发，速度为dx,dyzhen.问t秒钟后熊在哪里？其中每一秒中，熊的速度会增加所在位置的草莓数！

也就是dx(t)= dx(t-1)+x'+y',每一秒钟过后，每个方格内的草莓增加1,那么dx(t)= dx(t-1)+sx(t-1)+sy(t-1)+t-1

题目分析:根据题意得dx(t)= dx(t-1)+sx(t-1)+sy(t-1)+t-1 而sx(t)=sx(t-1)+dx(t);

纵坐标也相同，那么dy(t)= dy(t-1)+sx(t-1)+sy(t-1)+t-1,而sy(t)=sy(t-1)+dy(t);

而时间t=t-1+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

代入sx(t)=sx(t-1)+dx(t); sx(t)=2\*sx(t-1)+dx(t-1)+sy(t-1)+t-1+2;

同理sy(t)=2\*sy(t-1)+dy(t-1)+sx(t-1)+t-1+2;

则：

sx(t)           2    1    1    0     1     2      sx(t-1)

sy(t)          1    2    1    0     1     2       sy(t-1)

dx(t)          1    1    1    0     1     2       dx(t-1)

dy(t)          1   1     0     1     1     2      dy(t-1)

t                0    0    0    0     1     1         t-1

1              0    0    0    0     0      1          1

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #define ll long long
    using namespace std;
    
    ll mod;
    ll n,sx,sy,dx,dy;
    ll t;
    struct matrix
    {
        ll f[10][10];
        matrix operator*(struct matrix a) {
            struct matrix ans;
            for (int i=1;i<=6;i++) {
                for (int j=1;j<=6;j++) {
                    ans.f[i][j]=0;
                    for (int k=1;k<=6;k++) {
                        ans.f[i][j]=(ans.f[i][j]+f[i][k]*a.f[k][j]+mod)%mod;
                    }
                }
            }
            return ans;
        }
    }a,b;
    matrix fast_pow(struct matrix base,ll k)
    {
        struct matrix ans;
        for (int i=0;i<10;i++) {
            for (int j=0;j<10;j++) {
                if (i==j) ans.f[i][j]=1;
                else ans.f[i][j]=0;
            }
        }
        while (k) {
            if (k&1)
                ans=ans*base;
            base=base*base;
            k>>=1;
        }
        return ans;
    }
    void init()
    {
        b.f[1][1]=2;b.f[1][2]=1;b.f[1][3]=1;b.f[1][4]=0;b.f[1][5]=1;b.f[1][6]=2;
        b.f[2][1]=1;b.f[2][2]=2;b.f[2][3]=0;b.f[2][4]=1;b.f[2][5]=1;b.f[2][6]=2;
        b.f[3][1]=1;b.f[3][2]=1;b.f[3][3]=1;b.f[3][4]=0;b.f[3][5]=1;b.f[3][6]=2;
        b.f[4][1]=1;b.f[4][2]=1;b.f[4][3]=0;b.f[4][4]=1;b.f[4][5]=1;b.f[4][6]=2;
        b.f[5][1]=0;b.f[5][2]=0;b.f[5][3]=0;b.f[5][4]=0;b.f[5][5]=1;b.f[5][6]=1;
        b.f[6][1]=0;b.f[6][2]=0;b.f[6][3]=0;b.f[6][4]=0;b.f[6][5]=0;b.f[6][6]=1;
        a.f[1][1]=sx;a.f[2][1]=sy;a.f[3][1]=dx;a.f[4][1]=dy;a.f[5][1]=0;a.f[6][1]=1;
    }
    int main()
    {
        while (scanf("%lld%lld%lld%lld%lld%lld",&n,&sx,&sy,&dx,&dy,&t)!=EOF) {
            mod=n;
            sx--,sy--;
            init();
            struct matrix cur,ans;
            cur=b;
            ans=fast_pow(cur,t);
            ans=ans*a;
            printf("%lld %lld\n",ans.f[1][1]+1,ans.f[2][1]+1);
        }
        return 0;
    }