【BZOJ2476】战场的数目 矩阵乘法

【BZOJ2476】战场的数目

Description

Input

输入文件最多包含25组测试数据，每个数据仅包含一行，有一个整数p（1<=p<=10），表示战场的图形周长。p=0表示输入结束，你的程序不应当处理这一行。

Output

对于每组数据，输出仅一行，即满足条件的战场总数除以987654321的余数。

Sample Input

7
8
9
10
0

Sample Output

0
2
0
9

HINT

湖南省第六届大学生计算机程序设计竞赛

题解：我们先将周长>>=1，那么设f[i]表示：长+宽=i时的方案数。由于我们很容易求出战场是一整个矩形的方案数，所以我们可以先不考虑战场不能为矩形这个条件。

然后思考如何转移，一开始想按列转移，推出一个优美的式子，但是化简不了，结果发现要按行转移。

考虑最下面一行，如果左右两端的高度都>1，那么我们可以直接将最后一行扔掉，方案数变成f[i-1]。
如果左右两端有一端高度>1，那么我们可以将那一列扔掉，方案数变成2*f[i-1]。
如果左右两端高度都是1，那么我们将两边都扔掉，但是这种情况在上面已经被计算2次了，所以方案数要减去2*f[i-2]。

所以f[i]=3*f[i-1]-f[i-2]，矩乘搞一搞~

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long ll;

const ll mod=987654321;

struct M

{

	ll v[5][5];

	M (){memset(v,0,sizeof(v));}

	ll * operator [](int x)	{return v[x];}

	M operator * (M a)

	{

		M ret;

		for(int i=1;i<=3;i++)	for(int j=1;j<=3;j++)	for(int k=1;k<=3;k++)	(ret[i][j]+=v[i][k]*a[k][j])%=mod;

		return ret;

	}

};

M beg,ans,tr,x;

void pm(int y)

{

	ans=beg,x=tr;

	while(y)

	{

		if(y&1)	ans=ans*x;

		x=x*x,y>>=1;

	}

}

int main()

{

	tr[1][1]=3,tr[2][1]=-1,tr[2][3]=1,tr[1][2]=1;

	beg[1][1]=5,beg[1][2]=2,beg[1][3]=1;

	int p;

	while(1)

	{

		scanf("%d",&p);

		if(!p)	return 0;

		if(p&1)

		{

			printf("0\n");

			continue;

		}

		p>>=1;

		if(p<=3)

		{

			printf("0\n");

			continue;

		}

		pm(p-4);

		printf("%lld\n",(ans[1][1]-(p-1)+2*mod)%mod);

	}

	return 0;

}

//8 10 0