原题链接

这道题要求n=500，正解是要优化矩阵乘法过程使得复杂度降为$n^2$

我在本地开MAXN=510跑样例会re（程序无输出结果且不终止）；而在remote oj提交却是可以ac的。

然后尝试令MAXN=110，在本地就正常了。

这可能是什么原因导致的？

如下是MAXN=510的ac程序：

#include<cstdio>
#include<cmath>
#include<iostream>

#define pc(x) putchar(x)
#define ll long long

using namespace std;

const int MAXN=500+10;//就是这个数组大小的问题

int n,m,d,k;

struct mat
{
	int p,q;
	ll a[MAXN][MAXN];
	mat(int P=0,int Q=0)
	{
		p=P;q=Q;
		for(int i=1;i<=p;++i)
			for(int j=1;j<=q;++j)
				a[i][j]=0;
	}
	mat operator * (const mat &y) const
	{
		mat z=mat(p,y.q);
		if(z.p==z.q)
		{
			for(int j=1;j<=z.q;++j)
				for(int k=1;k<=q;++k)
					z.a[1][j]=(z.a[1][j]+a[1][k]*y.a[k][j])%m;
			for(int i=2;i<=z.p;++i)
			{
				z.a[i][1]=z.a[i-1][z.q];
				for(int j=2;j<=n;++j)
					z.a[i][j]=z.a[i-1][j-1];
			}
		}
		else
		{
			for(int i=1;i<=z.p;++i)
				for(int j=1;j<=z.q;++j)
					for(int k=1;k<=q;++k)
						z.a[i][j]=(z.a[i][j]+a[i][k]*y.a[k][j])%m;
		}
		return z;
	}
	void print()
	{
		for(int i=1;i<=p;++i)
		{
			for(int j=1;j<=q;++j)
			{
				printf("%lld",a[i][j]);
				if(j!=q)pc(' ');
			}
			pc('\n');
		}
	}
}A,ANS;

void solve()
{
	mat A=mat(n,n);
	mat ANS=mat(1,n);
	
	for(int j=1;j<=n;++j)
	{
		scanf("%lld",&ANS.a[1][j]);
		ANS.a[1][j]%=m;
	}
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			A.a[i][j]=(abs(i-j)<=d || abs(i-(j-n))<=d || abs(j-(i-n)<=d));
	
	while(k)
	{
		if(k&1)ANS=ANS*A;
		A=A*A;
		k>>=1;
	}
	
	ANS.print();
}

int main()
{
//	freopen("in.in","r",stdin);
	while(scanf("%d %d %d %d",&n,&m,&d,&k)!=-1)solve();
	return 0;
}