狀態變化 ?(x,y,dx,dy,i) 表示i時刻熊站在(x,y)處速度向量(dx,dy)下一個狀態是 ( 2x+y+dx+i , x+2y+dy+i , x+y+dx , x+y+dy , i+1 )

為了方便可以把平面從(1,1)平移到(0,0) ?這時速度需要+2 (因為速度每次+x+y ?x和y都-1則速度都+2)矩陣對應常數的地方為2

轉移矩陣：{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} #include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;const double g=10.0,eps=1e-9; const int N=10+5,maxn=1<<10+5,inf=0x3f3f3f3f;struct Node{ll row,col;ll a[N][N]; }; ll n; Node mul(Node x,Node y) {Node ans;ans.row=x.row,ans.col=y.col;memset(ans.a,0,sizeof ans.a);for(ll i=0;i<x.row;i++)for(ll j=0;j<x.col;j++)for(ll k=0;k<y.col;k++)ans.a[i][k]=(ans.a[i][k]+x.a[i][j]*y.a[j][k]+n)%n;return ans; } Node quick_mul(Node x,ll n) {Node ans;ans.row=x.row,ans.col=x.col;memset(ans.a,0,sizeof ans.a);for(ll i=0;i<ans.col;i++)ans.a[i][i]=1;while(n){if(n&1)ans=mul(ans,x);x=mul(x,x);n>>=1;}return ans; } int main() {ios::sync_with_stdio(false);cin.tie(0);// cout<<setiosflags(ios::fixed)<<setprecision(2); ll x,y,dx,dy,t;cin>>n>>x>>y>>dx>>dy>>t;x--,y--;Node A;A.row=6,A.col=6;A.a[0][0]=2,A.a[0][1]=1,A.a[0][2]=1,A.a[0][3]=0,A.a[0][4]=1,A.a[0][5]=2;A.a[1][0]=1,A.a[1][1]=2,A.a[1][2]=0,A.a[1][3]=1,A.a[1][4]=1,A.a[1][5]=2;A.a[2][0]=1,A.a[2][1]=1,A.a[2][2]=1,A.a[2][3]=0,A.a[2][4]=1,A.a[2][5]=2;A.a[3][0]=1,A.a[3][1]=1,A.a[3][2]=0,A.a[3][3]=1,A.a[3][4]=1,A.a[3][5]=2;A.a[4][0]=0,A.a[4][1]=0,A.a[4][2]=0,A.a[4][3]=0,A.a[4][4]=1,A.a[4][5]=1;A.a[5][0]=0,A.a[5][1]=0,A.a[5][2]=0,A.a[5][3]=0,A.a[5][4]=0,A.a[5][5]=1;A=quick_mul(A,t);Node B;B.row=6,B.col=1;B.a[0][0]=x,B.a[1][0]=y,B.a[2][0]=dx,B.a[3][0]=dy,B.a[4][0]=0,B.a[5][0]=1;B=mul(A,B);cout<<(B.a[0][0]+n)%n+1<<" "<<(B.a[1][0]+n)%n+1<<endl;return 0; } View Code

?

轉載于:https://www.cnblogs.com/acjiumeng/p/6881923.html

總結

以上是生活随笔為你收集整理的codefroce385E矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。