POJ3150 – Cellular Automaton(循环矩阵快速幂)

题目链接：POJ3150

【题意】给出一个有N(<=500)个数字的数列，求置换，每次置换为当前元素加上左右两边的d(<n/2)个数的和；

【分析】对于N=5，d=1，很容易推出一个N*N的矩阵：
1 1 0 0 1
1 1 1 0 0
0 1 1 1 0
0 0 1 1 1
1 0 0 1 1
如果直接用这个矩阵做快速幂的话，时间复杂度是log(k)*N^3的，肯定超时了；
那么必须要优化，观察上面矩阵发现，这个矩阵的下一行是上一行右移一个单位；这样的话就可以在矩阵乘法的时候只保存第一行，假如用a[]，保存第一行，则它做乘法的时候只需要a[i]*a[(i-1)%n]即可，因为上下左右都是循环的；
这样复杂度就降低到了log(k)*N^2,不会超时了；据说还有log(k)*N*log(N)的算法，表示想不到，以后再说；

【AC CODE】2282ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 500+10;
int n, MOD,a[MAXN],buf[MAXN];

void mul(int *ans, int *a, int *b)
{
	clc(buf,0);
	rep(i,0,n)
	{
		rep(s,0,n)
		{
			int j = (i-s+n)%n;
			buf[i] += (LL)a[j]*(LL)b[s]%MOD;
		}
		buf[i] %= MOD;
	}
	memcpy(ans,buf,sizeof(int)*n);
}
void pow_mod(int *ans, int *x, int c)
{
	int tmp[MAXN];
	clc(tmp,0);
	tmp[0] = 1;
	while(c)
	{
		if(c&1) mul(tmp,tmp,x);
		mul(x,x,x);
		c >>= 1;
	}
	memcpy(ans,tmp,sizeof(int)*n);
}
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int d,k,x[MAXN];
	while(~scanf("%d %d %d %d%*c", &n, &MOD, &d, &k))
	{
		clc(x,0);
		rep(i,0,n) scanf("%d%*c", &a[i]);
		repe(i,0,d) x[i] = 1;
		rep(i,n-d,n) x[i] = 1;
		pow_mod(x,x,k);
		mul(x,x,a);
		printf("%d", x[0]);
		rep(i,1,n) printf(" %d", x[i]);
		putchar('\n');
	}
	return 0;
}