CodeForces 385 E.Bear in the Field（dp+矩阵快速幂）

Description
一块n*n的草莓田，第i行第j列有i+j丛草莓，每秒每块田里的草莓丛数加一，一只熊初始在(sx,sy)处，初始速度为(dx,dy)，熊吃了当前位置的草莓，假设有k丛，那么其速度会变成(dx+k,dy+k)，熊当前在(x,y)则下一步会走到((x-1+dx)%n+1,(y-1+dy)%n+1)，问t秒后熊的位置
Input
六个整数n,sx,sy,dx,dy,t
(1<=n<=1e9,1<=sx,sy<=n,-100<=dx,dy<=100,0<=t<=1e18)
Output
输出两个整数ex ey表示t秒后熊的位置
Sample Input
5 1 2 0 1 2
Sample Output
3 1
Solution

Code

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=7;
struct Mat
{
    int mat[maxn][maxn];//矩阵 
    int row,col;//矩阵行列数 
};
Mat mod_mul(Mat a,Mat b,int p)//矩阵乘法 
{
    Mat ans;
    ans.row=a.row;
    ans.col=b.col;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=0;i<ans.row;i++)      
        for(int k=0;k<a.col;k++)
            if(a.mat[i][k])
                for(int j=0;j<ans.col;j++)
                    ans.mat[i][j]=(ans.mat[i][j]+(ll)a.mat[i][k]*b.mat[k][j])%p;
    return ans;
}
Mat mod_pow(Mat a,ll k,int p)//矩阵快速幂 
{
    Mat ans;
    ans.row=a.row;
    ans.col=a.col;
    for(int i=0;i<a.row;i++)
        for(int j=0;j<a.col;j++)
            ans.mat[i][j]=(i==j);
    while(k)
    {
        if(k&1)ans=mod_mul(ans,a,p);
        a=mod_mul(a,a,p);
        k>>=1;
    }
    return ans;
}
Mat A,B;
int a[maxn][maxn]={{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()
{
    A.row=A.col=6;
    for(int i=0;i<6;i++)
        for(int j=0;j<6;j++)
            A.mat[i][j]=a[i][j];
    int n,sx,sy,dx,dy;
    ll t;
    while(~scanf("%d%d%d%d%d%I64d",&n,&sx,&sy,&dx,&dy,&t))
    {
        B.row=6,B.col=1;
        B.mat[0][0]=sx-1;
        B.mat[1][0]=sy-1;
        B.mat[2][0]=(dx%n+n)%n;
        B.mat[3][0]=(dy%n+n)%n;
        B.mat[4][0]=0;
        B.mat[5][0]=1;
        B=mod_mul(mod_pow(A,t,n),B,n);
        printf("%d %d\n",B.mat[0][0]+1,B.mat[1][0]+1);
    }
    return 0;
}