程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3150 Cellular Automaton（矩陣快速冪）

poj 3150 Cellular Automaton（矩陣快速冪）

編輯：C++入門知識

大致題意：給出n個數，問經過K次變換每個位置上的數變為多少。第i位置上的數經過一次變換定義為所有滿足 min( abs(i-j),n-abs(i-j) )<=d的j位置上的數字之和對m求余。

思路：

我們先將上述定義表示為矩陣

B =

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

B[i][j] = 表示i與j滿足上述關系，B[i][j] = 0表示i與j不滿足上述關系。根據這個矩陣，那麼樣例1中1 2 2 1 2經過一次變換變成了5 5 5 5 4。

其實這也是矩陣相乘的問題，令A = 1 2 2 1 2，那麼A * B = 5 5 5 5 4。那麼要經過K次變換，答案無疑是 A*（B^k）mod m。

用矩陣快速冪的復雜度為 O(n^3 * log k),n最大是500，K也很大，必會TLE。logk是不會變了，優化在於n^3。仔細觀察B矩陣，發現它是有規律的，它的每一行都是它上一行右移一位得到的。那麼在矩陣相乘時，我們只需計算第一行，然後整個矩陣就算出來了，這樣復雜度降為O(n^2 * log k)。

#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 510;

int n,m,d,k;

_LL c[maxn][maxn];
_LL a[maxn][maxn],b[maxn];


int main()
{
	while(~scanf(%d %d %d %d,&n,&m,&d,&k))
	{
		for(int i = 0; i < n; i++)
			scanf(%I64d,&b[i]);

		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if( min(abs(i-j),n-(abs(i-j))) <= d)
					a[i][j] = 1;
				else a[i][j] = 0;
			}
		}

		while(k)
		{
			if(k&1)
			{
				for(int i = 0; i < n; i++)
				{
					c[0][i] = 0;
					for(int j = 0; j < n; j++)
					{
						c[0][i] += b[j]*a[j][i];
					}
				}
				for(int i = 0; i < n; i++)
					b[i] = c[0][i]%m;
			}

			for(int i = 0; i < 1; i++)
			{
				for(int j = 0; j < n; j++)
				{
					c[i][j] = 0;
					for(int k = 0; k < n; k++)
						c[i][j] += a[i][k]*a[k][j];
				}
			}
			for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					if(i == 0)
						a[i][j] = c[i][j]%m;
					else a[i][j] = a[i-1][(j-1+n)%n];
				}
			}

			k >>= 1;
		}
		for(int i = 0; i < n-1; i++)
			printf(%I64d ,b[i]);
		printf(%I64d
,b[n-1]);

	}
	return 0;
}