[洛谷P5023][题解]填数游戏

0.一些东西

原题NOIp2018
毒瘤找规律差评

1.解法

这道题数据较小，可以暴力打表找规律（没打）。
当然正解是数学推导，我们接下来大致讲一下思路。
注：下文中“对角线”均指左下-右上（副对角线）。
首先给出两个引理及简略证明：
引理1：任一对角线从左下到右上填数单调不增。
证明很简单，照题意模拟即可，此处不再赘述。
引理2：若\((x,y-1)\)与\((x-1,y)\)填数相同，则以\((x,y)\)为左上角的矩形每条对角线上填数分别相同。
证：可运用反证法，设在对应矩形（红框）中出现了对角线上填数不等的情况，

蓝色与黄色路径即不满足题意，证毕。
设最终答案为\(ans(n,m)\)，
于是我们通过打表可得：
1.\(ans(n,m)=ans(m,n)\)；
证：将\(n\times m\)的矩形和填的数都反过来，可以理解为将每条路径的\(w\)和\(s\)均反过来，结果显然不变。
2.\(ans(n,m+1)=3\times ans(n,m)\)。
证明留作练习。（其实是我也不会证，以后补上这里）

由于有了两个引理中的限制，我们可以手玩每种情况，算出答案。
情况1：\(n=m\)，此时有如下几种情况。

答案为\(8^{n-1}\)；

答案为\(5\times 2^{3n-7}\)；

这种情况不太好办，我们发现左边的两列不确定性太大，不能直接计算。
但是我们可以枚举！方式为枚举到哪条绿线出现了相同填数。
这样我们就可以算出这种情况的答案，做一个等比数列求和即可得到答案。
（不写了不写了）；

与上面是完全对称的，可以直接套用。

此时就可以推出\(ans(n,n)\)了。（累死了直接放结果）
\(\frac{83\times8^n+5\times2^{n+7}}{384}\)
\(ans(n,n+1)\)同理，\(\frac{83\times8^{n}+2^{n+8}}{128}\)。

此时请注意，我们刚刚推的都是\(n\ge4\)的情况，其余情况如下：
\(n=1,ans(1,m)=2^m;\)
\(n=2,ans(2,m)=4\times3^{m-1};\)
\(n=3,ans(3,m)=112\times3^{m-3};\)
这样就可以推出任意\(ans(n,m)\)了。

2.代码

#define mod 1000000007
int n,m;
inline int pw(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod,b>>=1;
	}
	return ans;
}
signed main(){
	Read(n),Read(m);
	if(n>m)swap(n,m);
	if(n==1)cout<