【bzoj2476】战场的数目 矩阵乘法优化dp

题目描述

（战场定义为对于最高的一列向两边都严格不增的“用积木搭成”的图形）

输入

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

输出

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

样例输入

7
8
9
10
0

样例输出

0
2
0
9

---

题解

矩乘优化dp的一道神题。

显然答案=总数-矩形个数。

设$f[i]$表示周长为$2i$的方案数。

那么如果左右都没有高度为1的，那么可以删掉最下边一行，为$f[i-1]$。

如果左边或右边有高度为1的，那么可以删掉这一个，为$f[i-1](*2)$。

而如果左右都有高度为1的，那么可以删掉这两个，为$f[i-2]$，这种情况会重复计算，应该减去。

最后的状态转移方程即为$f[i]=3f[i-1]-f[i-2]$，使用矩乘加速转移即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod = 987654321;

struct data

{

	ll v[2][2];

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

	data(int x) {memset(v , 0 , sizeof(v)) , v[0][0] = v[1][1] = 1;}

	data operator*(const data a)const

	{

		data ans;

		int i , j , k;

		for(i = 0 ; i < 2 ; i ++ )

			for(j = 0 ; j < 2 ; j ++ )

				for(k = 0 ; k < 2 ; k ++ )

					ans.v[i][j] = (ans.v[i][j] + v[i][k] * a.v[k][j]) % mod;

		return ans;

	}

	data operator^(const ll a)const

	{

		data x = *this , ans(1);

		ll y = a;

		while(y)

		{

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

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

		}

		return ans;

	}

}A , B;

int main()

{

	A.v[0][0] = A.v[0][1] = 1;

	B.v[0][1] = mod - 1 , B.v[1][0] = 1 , B.v[1][1] = 3;

	ll p;

	while(~scanf("%lld" , &p) && p)

	{

		if(p & 1 || p == 2) printf("0\n");

		else printf("%lld\n" , ((A * (B ^ (p / 2 - 1))).v[0][0] - p / 2 + 1 + mod) % mod);

	}

	return 0;

}