首页 > 代码库 > POJ 3233

POJ 3233

二分二分二分。。记录二分的点。1600多MS,应该 可以再优化

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int stack[150],sp;int n,M;struct Matrax {	int m[35][35];};Matrax operator +( Matrax A, Matrax B){	Matrax ret;	for(int i=0;i<n;i++)	for(int j=0;j<n;j++)	ret.m[i][j]=(A.m[i][j]+B.m[i][j])%M;	return ret;}Matrax a,per;void initial(){	int i,j;	for(i=0;i<n;i++){		for(j=0;j<n;j++){			scanf("%d",&a.m[i][j]);			a.m[i][j]%=M;			per.m[i][j]=(i==j);		}	}}Matrax multi(Matrax a,Matrax b){	Matrax c;	int k,i,j;	for(i=0;i<n;i++){		for(j=0;j<n;j++){			c.m[i][j]=0;			for(k=0;k<n;k++){				c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;			}			c.m[i][j]%=M;		}	}	return c;}Matrax Power(int k){	Matrax c,p,ans=per;	p=a;	while(k){		if(k&1){			ans=multi(ans,p);			k--;		}		else {			k/=2;			p=multi(p,p);		}	}/*	for(int i=0;i<n;i++){	for(int j=0;j<n;j++)	cout<<‘ ‘<<ans.m[i][j];	cout<<endl;	}*/	return ans;}int main(){	int k;	while(scanf("%d%d%d",&n,&k,&M)!=EOF){		initial();		sp=-1;		stack[++sp]=k;		while(k!=1){			if(k%2){				k--;				stack[++sp]=k;			}			else{			stack[++sp]=k/2;			k/=2;			}		}/*		for(int i=0;i<=sp;i++)		cout<<stack[i]<<‘ ‘;		cout<<endl;*/		Matrax ans=a;		for(int i=sp;i>=1;i--){			if(stack[i]+1==stack[i-1]){				ans=ans+Power(stack[i-1]);			}			else if(stack[i]*2==stack[i-1]){				ans=ans+multi(ans,Power(stack[i]));			}	/*				for(int s=0;s<n;s++){			printf("%d",ans.m[s][0]%M);			for(int t=1;t<n;t++)			printf(" %d",ans.m[s][t]%M);			printf("\n");		}*/		}		for(int s=0;s<n;s++){			printf("%d",ans.m[s][0]%M);			for(int t=1;t<n;t++)			printf(" %d",ans.m[s][t]%M);			printf("\n");		}	}	return 0;}

  

POJ 3233