#include <stdio.h>
int n,m,c[512],a[512][512],result[512][512];
/*
处理矩阵Ａ和Ｂ的乘机．并将结果存入Ａ中。
*/
void fun(int a[][512],int b[][512])
{
	int w[512][512],i,j,k;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			w[i][j]=0;
			for(k=0;k<n;k++)
			{
				w[i][j]+=a[i][k]*b[k][j];
				if(w[i][j]>=m) w[i][j]%=m;
			}
		}
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			a[i][j]=w[i][j];
}
int main()
{
	int d,k,i,len,j,pos,digit,s,count;
	while(scanf("%d%d%d%d",&n,&m,&d,&k)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%d",&c[i]);
		len=(d<<1)+1;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;a[i][j]=0,result[i][j]=0,j++);
			result[i][i]=1;
		}
　　　　　　　　　/*生成矩阵*/
		for(i=0;i<n;i++)
			for(j=(i+n-d)%n,count=0;count<len;count++)
			{
				a[j][i]=1;
				j++;
				if(j>=n) j%=n;
			}
　　　　　　　　　/*求出k的二进制位数，例如，２的二进制数为１０，长度为２，这里得出３，比长度多１*/
		pos=digit=1;
		while(k>=digit)
		{
			digit<<=1;
			pos++;
		}

		digit=1;
　　　　　　　　　/*测试k的每个位，如果为１，则乘以矩阵Ａ，然后矩阵Ａ再做平方*/
		for(i=1;i<pos;i++)
		{
			if(k&digit)
				fun(result,a);
			digit<<=1;
			fun(a,a);
		}
		for(i=0;i<n;i++)
		{
			for(s=j=0;j<n;j++)
			{
				s+=c[j]*result[j][i];
				if(s>=m) s%=m;
			}
			if(i<n-1)
				printf("%d ",s);
			else printf("%d\n",s);
		}
	}
	return 0;
}

• Re:你的时间复杂度太高，O(N^3logk)要超时，错误先来不及看 (81) a024014 2007-03-22 19:14:50
  • 矩阵的特点是可以把乘法复杂度降到O(N^2)的 (0) YUMEN19850720 2007-03-23 09:25:46
    • Re:矩阵的特点是可以把乘法复杂度降到O(N^2)的 (12) a024014 2007-03-24 11:46:37
    • Re:矩阵的特点是可以把乘法复杂度降到O(N^2)的 (21) RainyMiss 2009-09-09 19:22:08