NOIP2018提高组填数游戏

https://www.luogu.com.cn/problem/P5023

首先要意识到这不是一个状压而是一个分类大讨论数学题。
定义对角线时左下到右上的对角线

发现性质

1. 每一条对角线上填的数是单调不增的。
2. 如果(x-1,y)和(x,y-1)的填的数相同，那么以(x,y)为左上角、以整个矩阵的右下角为右下角的子矩阵内所有对角线内的填数各自相同。

令 $Ans(n,m)$ 表示宽为 $m$ 高为 $n$ 的矩阵填数方案，则 $Ans(n,m)=Ans(m,n)$ 。
怎么证明呢?
对于任意一个 m > n 的方案，都有一个唯一对应的 m < n 的方案
将填入的数全部反转，然后将整个矩阵顺时针转90°，最后把矩阵左右轴对称一下可以得到一个等价方案

对于 $n \ge 4$ 我们分 $4$ 种情况讨论
1.最上面的两个填数相同

2.最上面的两个数不同，下面一条对角线的3个填数相同

3.3个填数为1，0，0

4.3个填数为1，1，0

无论是哪种情况，总是会存在一个点(x,y)使得(x-1,y)和(x,y-1)填数相同，

然后可以得到 对于任意的 $n \ge 4 \& m \ge n + 1$ ,有 $Ans(n, m + 1) = 3 * Ans(n, m)$

然后慢慢推就能得到答案了。。
之后3种也类似

$case_1 = 8^{n - 1} \\ case_2 = 5 \times 2 ^ {3n - 7}\\ case_3 = 2\times 4\times 5\times \sum _{i=0}^{n−5}4^i\times 2^{n−1}+2\times 4\times 3\times 2^{n−2}+2\times 3\times 2^{n−2}\\ case_4 = cast_3$

$Ans(n, n) = \frac{83 \times 8 ^ n + 5 \times 2 ^{n + 7}}{384}$

其他3个结论类似

#include <bits/stdc++.h>
using namespace std;

const int P = 1e9 + 7;
inline long long qpow(long long a, long long b)
{
	long long res = 1;
	while (b)
	{
		if (b & 1) res = res * a % P;
		b >>= 1;
		a = a * a % P;
	}
	return res;
}
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	if (n > m)
		swap(n, m);
	if (n == 1)
		printf("%lld", qpow(2, m));
	else if (n == 2)
		printf("%lld", 4 * qpow(3, m - 1) % P);
	else if (n == 3)
		printf("%lld", 112 * qpow(3, m - 3) % P);
	else
	{
		if (m == n)
			printf("%lld", (83 * qpow(8, n) % P + 5 * qpow(2, n + 7) % P) * 190104168 % P);
		else
			printf("%lld", (83 * qpow(8, n) % P + qpow(2, n + 8)) * qpow(3, m - n - 1) % P * 570312504 % P);
	}
	return 0;
}