)复杂度不能推出的数，果断想到快速幂，不过题里说得实在是太清楚了，连递推的矩阵都给出来了。
代码：
?
int main()
{
int tot;
while(scanf(%d,&tot)&&~tot)
{
Matrix a;
a.m=a.n=2;
a.a[0][0]=a.a[0][1]=a.a[1][0]=1;
a.a[1][1]=0;
if(tot==0)
printf(0
);
else
{
Matrix ans=M_quick_pow(a,tot);
printf(%d
,ans.a[0][1]);
}
}
return 0;
}
类型六：DP加速
题目：Warcraft III 守望者的烦恼
链接：https://vijos.org/p/1067
题意：给出k,n(1<=k<=10,1<=n<=2^31-1).每一步可以走1~k的距离，求走到n距离有多少种走法。
思路：如果只是单纯的DP的话，复杂度是O(N^2)，公式是dp[i]=dp[i-1]+dp[i-2]+...+dp[i-k]。可以用矩阵快速幂来加速。
不断用矩阵左乘，就可以用快速幂来加速了。
代码：
?
#define maxn 15
#define maxm 15
#define MOD 7777777
struct Matrix
{
int n,m;//n是列数,m是行数
LL a[maxn][maxm];
void init()
{
n=m=0;
memset(a,0,sizeof(a));
}
void change(int c)
{
n=c;
m=c;
memset(a,0,sizeof(a));
for(int i=0;i
>=1;
m.Copy(m*m);
}
return tmp;
}
int main()
{
Matrix A,ans;
int k,n;
scanf(%d%d,&k,&n);
A.change(k);
ans.init();
ans.n=k;
ans.m=1;
ans.a[0][0]=1;
A.Copy(M_quick_pow(A,n));
ans.Copy(A*ans);
printf(%I64d
,ans.a[0][0]);
return 0;
}
?
种类七：路径种类数
题目一：How many ways??
链接：http://acm.hdu.edu.cn/showproblem.php?pid=2157
题意：给出n个节点m条单向边(0 < n <= 20, m <= 100)，问从s点到t点经过k个其他节点有多少种走法。
思路：用临接矩阵A记录路径，记录的路径也表示从i到j是否能一次到达。B=A*A表示的是i到j能两次到达的走法。B[i][j]=ΣA[i][k]*A[k][j]。
P.S.好像很早刚学临接矩阵的时候就想过这种用法，到这实现了。
代码：
?
int main()
{
Matrix A,ans[25];
int a,b,c,x,y,z;
while(scanf(%d%d,&a,&b))
{
if(a+b==0)
break;
A.init();
A.m=a;
A.n=a;
for(int i=0; i
类型七点五：路径种类数变种
题目：Cow Relays
链接： http://poj.org/problem?id=3613
题意：给出起点S和终点E，求从S到E的N步最短路（经过N个节点）。
思路：弗洛伊德算法的“慢动作”，A矩阵的a[i][j]代表经过a个节点的最短路，B矩阵的a[i][j]代表经过b个节点的最短路，那么C矩阵的a[i][j]的弗洛伊德结果就是经过了a+b个节点的最短路，如果经过a+b个节点不能到达，那么就是INF。因为N极大，所以递推O(N)也会超时，用到了矩阵快速幂。
P.S.我开的布尔数组默认值不是false，需要我自己重置一下才可以，WA一发。
代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include