POJ 3233( 3233 Matrix Power Series 矩阵的快速幂 )

spoiler posted @ 2011年4月25日 21:32 in 十个利用矩阵乘法解决的经典题目 , 1753 阅读

题目分析:

S = A + A2 + A3 + … + Ak.

求 S mod p;

我们要二分考虑

二分求$$A^k$$mod p

首先把$$A^k$$转化成:

                     1) 如果k是偶数 ( $$A^{\frac{k}{2}}$$ mod p ) * ( $$A^{\frac{k}{2}}$$ mod p )这样就把就达到了降幂的作用

                      2)如果k是奇数 ( $$A^{\frac{k}{2}}$$ mod p ) * ( $$A^{\frac{k}{2}}$$ mod p )* ( A mod p)

然后再对求和的过程进行二分!

如果K是偶数我们把公式转换成 S=A + A2 + A3 + … + $$A^{\frac{k}{2}}$$+$$A^{\frac{k}{2}}$$*(A + A2 + A3 + … + $$A^{\frac{k}{2}}$$

如果K是奇数 则可以写成: S=A + A2 + A3 + … + $$A^{\frac{k}{2}+1}$$+$$A^{\frac{k}{2}+1}$$*(A + A2 + A3 + … + $$A^{\frac{k}{2}}$$

代码+部分注释:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M{
	int s[32][32];
};
int n,p;
struct M add(struct M a,struct M b){
	int i,j;
	struct M c;
	memset(c.s,0,sizeof(c.s));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			c.s[i][j]=(a.s[i][j]+b.s[i][j])%p;
	return c;
}
struct M multiply(struct M a,struct M b){
	int i,j,k;
	struct M c;
	memset(c.s,0,sizeof(c.s));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
	return c;
}
struct M paw(struct M a,int t){
	struct M b;
        memset(b.s,0,sizeof(b.s));
	if(t==0){
		for(int i=1;i<=n;i++)
			b.s[i][i]=1;
		return b;
	}
	else{
		struct M k=paw(a,t/2);
		if(t&1){
			return multiply(multiply(k,k),a);
		}
		else
			return multiply(k,k);
	}
}
struct M sum(struct M a,int t){
	if(t==1){
		return a;
	}
	else{
		struct M tempt=sum(a,t/2);
		if(t&1){
			struct M k=paw(a,t/2+1);
			return add(add(tempt,k),multiply(tempt,k));
		}
		else{
			return add(tempt,multiply(tempt,paw(a,t/2)));
		}
	}
}
int main(){
	int k,i,j;
	struct M a;
	cin>>n>>k>>p;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			scanf("%d",&a.s[i][j]);
			a.s[i][j]%=p;
		}
	struct M tempt=sum(a,k);
	for(i=1;i<=n;i++){
		for(j=1;j<n;j++){
			  cout<<tempt.s[i][j]<<" ";
		}
		printf("%d\n",tempt.s[i][j]);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter