本文主要是介绍HDU 1757,1575,2604,2256 矩阵快速幂总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 1757:
就是由f(x)可以得出矩阵……可以得到下面的a0到a9并上有1，0的矩阵，与f0到f9相乘一次可以得到f1到f10，所以^(k-9)次就可以得到fn-9到fn了，第一行就是f(k)……
这个图来自：http://www.cnblogs.com/wally/archive/2013/03/01/2938305.html
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define MN 3005
//#define INF 1000000007
#define eps 1e-7
using namespace std;
typedef long long ll;
#define Max 10
int INF;
struct Matrix //快速幂模板
{int m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,int n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
};
int main()
{int m,k;while(~scanf("%d%d",&k,&m)){int i,j=9,sum=0;INF=m;Matrix res;mem(res.m,0);for(i=0;i<10;i++)scanf("%d",&res.m[0][i]);if(k<10) {pri(k%m);continue;}for(i=1;i<10;i++)res.m[i][i-1]=1;res=quickpow(res,k-9);for(i=0;i<10;i++)sum=(sum+res.m[0][i]*(j--))%m;pri(sum);}return 0;
}
HDU 1575：
先求幂后再求主对角线的和。
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define Max 10
#define INF 9973
#define eps 1e-7
using namespace std;
typedef long long ll;
struct Matrix //快速幂模板
{int m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,int n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
};
int main()
{int t;sca(t);while(t--){int i,n,k,j=9,sum=0;scanf("%d%d",&n,&k);Matrix res;mem(res.m,0);for(i=0;i<n;i++)for(j=0;j<n;j++)sca(res.m[i][j]);res=quickpow(res,k);for(i=0;i<n;i++)sum=(sum+res.m[i][i])%INF;pri(sum);}return 0;
}
HDU 2604
分析;
解法一：同L=2时的状态递推出后面的状态：
其4个状态，分别是：fm,ff,mm,mf。
fm只可以到mm（因为fmf不符和要求了）
ff只可以到fm（同理）
mm可以到mm，mf
mf可以到fm，ff
所以构造的矩阵是
fm ff mm mf
fm 0 0 1 0
ff 1 0 0 0
mm 0 0 1 1
mf 1 1 0 0
解法二：同L=0到L=5值递推出来：
1 根据题目的意思，我们可以求出F[0] = 0 , F[1] = 2 , F[2] = 4 , F[3] = 6 , F[4] = 9 , F[5] = 15
2 那么根据上面前5项我们可以求出n >= 5的时候 F[n] = F[n-1]+F[n-3]+F[n-4]
那么我们就可以构造出矩阵
| 1 0 1 1 | | F[n-1] | | F[n] |
| 1 0 0 0 | * | F[n-2] | = | F[n-1] |
| 0 1 0 0 | | F[n-3] | | F[n-2] |
| 0 0 1 0 | | F[n-4] | | F[n-3] |
设上面构造矩阵为a，则为a^(l-4)*f[4]=f[l-4].
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define Max 4
//#define INF 9973
#define eps 1e-7
using namespace std;
typedef long long ll;
int INF;
struct Matrix //快速幂模板
{int m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,int n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
};
int main()
{int i,j,k,n;int a[6]={0,2,4,6,9,15},b[5]={9,6,4,2};while(~scanf("%d%d",&k,&n)){if(k<5) {pri(a[k]%n);continue;}Matrix res;mem(res.m,0);int sum=0;INF=n;res.m[0][0]=res.m[0][3]=res.m[0][2]=1;res.m[1][0]=res.m[2][1]=res.m[3][2]=1;res=quickpow(res,k-4);for(i=0;i<Max;i++)sum=(sum+res.m[0][i]*b[i])%INF; //乘以前一个1到4的矩阵pri(sum);}return 0;
}
HDU 2256
这题确实不是自己能会的题了，而且是看了别人的解题报告看了好久才明天啥意思……唉……数学退化太快了……
分析网址：http://blog.csdn.net/chenguolinblog/article/details/10212567
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define Max 2
#define INF 1024
#define eps 1e-7
using namespace std;
typedef long long ll;
//int INF;
struct Matrix //快速幂模板
{int m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,int n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
};
int main()
{int t,n,sum;sca(t);while(t--){sca(n);if(n==1) {pri(9);continue;}Matrix res;mem(res.m,0);res.m[0][0]=5,res.m[0][1]=12;res.m[1][0]=2,res.m[1][1]=5;res=quickpow(res,n-1);sum=(res.m[0][0]*5+res.m[0][1]*2)%INF;sum=(2*sum-1)%INF;pri(sum);}return 0;
}
这篇关于HDU 1757,1575,2604,2256 矩阵快速幂总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
