題目鏈接：點擊查看

題目大意：實現公式：

f(x)=x，x<10

f(x)=a0*f(x-1)+a1*f(x-2)+……+a9*f(x-10)

題目給出a0~a9，一個n和一個m，要求輸出f(n)對m取模后的結果

題目分析：水題

初始矩陣：(取n=10即可)

f(n-1)

f(n-2)

f(n-3)

f(n-4)

f(n-5)

f(n-6)

f(n-7)

f(n-8)

f(n-9)

f(n-10)

輔助矩陣：

a0	1	0	0	0	0	0	0	0	0
a1	0	1	0	0	0	0	0	0	0
a2	0	0	1	0	0	0	0	0	0
a3	0	0	0	1	0	0	0	0	0
a4	0	0	0	0	1	0	0	0	0
a5	0	0	0	0	0	1	0	0	0
a6	0	0	0	0	0	0	1	0	0
a7	0	0	0	0	0	0	0	1	0
a8	0	0	0	0	0	0	0	0	1
a9	0	0	0	0	0	0	0	0	0

?答案矩陣：

f(n)

f(n-1)

f(n-2)

f(n-3)

f(n-4)

f(n-5)

f(n-6)

f(n-7)

f(n-8)

f(n-9)

套模板即可，上代碼：

#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;int mod;const int N=10;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);int n;while(scanf("%d%d",&n,&mod)!=EOF){Ma ans;for(int i=0;i<10;i++)scanf("%d",&ans.a[i][0]);for(int i=0;i<9;i++)ans.a[i][i+1]=1;if(n<10){printf("%d\n",n%mod);continue;}Ma st;for(int i=0;i<10;i++)st.a[0][i]=9-i;ans=q_pow(ans,n-9);printf("%lld\n",(st*ans).a[0][0]);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 1757 A Simple Math Problem(矩阵快速幂，水题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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