Queuing HDU - 2604(矩阵快速幂)

L           K

 0          1

1          2
2          4
3          6
4          9
5          15
6          25
7          40
8          64
9          104
10          169
11          273
12          441
13          714
14          1156
15          1870
16          3025
17          4895
18          7921
19          12816

由上表可知f[n]=f[n-1]+f[n-3]+f[n-4];

转移矩阵为：

#include <bits/stdc++.h>
using namespace std;
struct node{
	int z[5][5];
};
int L, M;
int f[]={9, 6, 4, 2};
node mul(node a, node b){
	node c;
	for(int i=0; i<4; i++){
		for(int j=0; j<4; j++){
			c.z[i][j]=0;
			for(int k=0; k<4; k++){
				c.z[i][j]=(c.z[i][j]+a.z[i][k]*b.z[k][j])%M;
			}
		}
	}
	return c;
}
int Power(node a, int n){
	node t;
	for(int i=0; i<4; i++){
		for(int j=0; j<4; j++){
			if(i==j) t.z[i][j]=1;
			else t.z[i][j]=0;
		}
	}
	while(n){
		if(n&1) t=mul(t, a);
		a=mul(a, a);
		n>>=1;
	}
	int ans=0;
	for(int i=0; i<4; i++){
		ans=(ans+t.z[0][i]*f[i]%M)%M;
	}
	return ans;
}
int main(){
	while(cin >> L >> M){
		node a;
		memset(a.z, 0, sizeof(a.z));
		a.z[0][0]=a.z[0][2]=a.z[0][3]=a.z[1][0]=a.z[2][1]=a.z[3][2]=1;
		int	ans[]={1, 2, 4, 6, 9};
		if(L<5) cout << ans[L]%M << endl;
		else cout << Power(a, L-4) << endl;
	}
	return 0;
}

最后

以上就是刻苦便当为你收集整理的Queuing HDU - 2604(矩阵快速幂)的全部内容，希望文章能够帮你解决Queuing HDU - 2604(矩阵快速幂)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。