題目鏈接：點擊查看

題目大意：給出定義：

現(xiàn)在依次給出n,A0,AX,AY,B0,BX,BY

求Aod的第n項對1e9+7取模后的結(jié)果

題目分析：

簡單矩陣快速冪

首先化簡一下：

初始矩陣：（取n=1即可）

1

輔助矩陣：

1	0	0	0	0
1	AX*BX	0	0	0
0	AX*BY	AX	0	0
0	BX*AY	0	BX	0
0	AY*BY	AY	BY	1

答案矩陣：

1

注意幾個小坑：

需要特判n==0時輸出0

初始參數(shù)給的很大，相乘后需要立即取模，不然在運算的過程中會爆long long

然后套模板即可，上代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #define Pi acos(-1.0) using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int N=5;struct Ma {LL a[N][N];Ma(){memset(a,0,sizeof(a));}friend Ma operator*(const Ma& a,const Ma& b){Ma ans;for(int i=0;i<N;i++)for(int j=0;j<N;j++){ans.a[i][j]=0;for(int k=0;k<N;k++){ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;}}return ans;} };Ma q_pow(Ma a,LL b) {Ma ans;for(int i=0;i<N;i++)ans.a[i][i]=1;while(b){if(b&1)ans=ans*a;a=a*a;b>>=1;}return ans; }int main() { // freopen("input.txt","r",stdin);LL n;while(scanf("%lld",&n)!=EOF){LL a0,ax,ay,b0,bx,by;scanf("%lld%lld%lld%lld%lld%lld",&a0,&ax,&ay,&b0,&bx,&by);if(n==0)//特判0 {printf("0\n");continue;}Ma st;st.a[0][0]=0;st.a[0][1]=a0*b0%mod;//日常模一模st.a[0][2]=a0;st.a[0][3]=b0;st.a[0][4]=1;Ma ans;ans.a[0][0]=1;ans.a[1][0]=1;ans.a[1][1]=ax*bx%mod;//記得取模ans.a[2][1]=ax*by%mod;ans.a[3][1]=bx*ay%mod;ans.a[4][1]=ay*by%mod;ans.a[2][2]=ax;ans.a[4][2]=ay;ans.a[3][3]=bx;ans.a[4][3]=by;ans.a[4][4]=1;ans=q_pow(ans,n);printf("%lld\n",(st*ans).a[0][0]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4686 Arc of Dream(矩阵快速幂，水题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。