「Luogu P5023」填数游戏

NOIP2018 唯一没做出来的题

要是写完两题后直接去打暴力大概也不止50分吧

反正确实跪在这题了

Luogu P5023

题意

你有一个 $n$ 行 $m$ 列的矩阵，左上角为 $(0,0)$

每一个位置有一个数字 $0/1$

你需要从 $(0,0)$ 走到 $(n-1,m-1)$，只能向右或向下走 $(R/D)$，一共 $n+m-2$ 步，这会形成一条路径

把方向记下来可以得到同样长度的只包含 $R/D$ 的字符串 $w(P)$

并且经过的 $n+m-1$ 个位置的数字连起来可以得到一个 $01$ 串 $s(P)$

你需要求出有多少种填数的方案，使得对于任意两条路径 $P_1,P_2$，若 $w(P_1)>w(P_2)$，那么 $s(P_1)\le s(P_2)$

模 $10^9+7$

$n\le 8,m\le 10^6$

---

做法

转化

限制可以等价转化为下面两个条件

对于 $x+y$ 为定值的所有点 $(x,y)$，构成一条斜线，自左向右是连续的一段$0$加上连续的一段$1$，可以全部相同

这是因为一条到 $(x,y)$ 的路径向两个方向走的时候必须要有 $(x+1,y)$ 上的数字不大于 $(x,y+1)$

即任意 $(x,y)$ 不大于 $(x-1,y+1)$

若 $(x-1,y)$ 和 $(x,y-1)$ 上的数字相同，那么以 $(x,y)$ 为左上角的极大的子矩阵在一个斜行上的数字都相同，即对于 $a\ge x,b\ge y$的 $(a,b)$ 有约束

这是因为当 $(x-1,y)$ 和 $(x,y-1)$ 上的数字相同，从 $(x-1,y-1)$ 经过这两个位置再到 $(x,y)$ 的路径的 $01$ 串相同

也就是说到 $(x,y)$ 有至少两条 $01$ 串相同的路径

那么接下来的每一步必须相同，否则会存在不满足限制的路径

观察

显然 $n,m$ 交换并不会影响答案

下面只考虑$3\le n\le m$的情况，其余情况都可以简单计算

分类讨论

1. $(0,1)$ 和 $(1,0)$ 相同

以 $(1,1)$ 为左上角的矩形的斜线上数字都相同，只剩下 $(0,x)$ 和 $(x,0)$ 需要再判一下

2. $(0,2),(1,1)$ 和 $(2,0)$ 相同

和情况1差不多，多特判一条斜线就好了

3 & 4. $(1,1)$ 和 $(0,2),(2,0)$ 中的恰好一个相同

容易发现两种是对称的，下面只考虑有 $(2,0)$ 和 $(1,1)$ 是 $0$ 的情况

这时以 $(2,1)$ 为左上角的子矩阵斜线部分相同

也就是左边剩下一列，顶部剩下两行没有限制

再讨论

考虑这种情况

有 $5$ 种填法

0000, 0111 和 1111

好像这四种都一样..

这会使斜线区域在两步后扩大至前两种大情况中

0001

这会维持现状

也就是枚举一下在哪一个斜行选择什么方案，然后计算一下贡献就好了，可以通过预处理后缀

这5种情况并不是总是都存在，再判一下就好了

总时间复杂度 $\mathcal O(n+m)$

---

可以发现每一次的贡献都形如 $c*2^a3^b$，并且3,4两种情况都是连续的 $\mathcal O(1)$ 段等比数列，可以快速幂

总复杂度 $\mathcal O(\log n+\log m)$

---

代码

复杂度 $\mathcal O(n+m)$

代码中矩形是从 $(1,1)$ 到 $(n,m)$

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

const int N = 1000015, P = 1000000007;
int n, m, ans, a[N], f[N];
int main() {
	scanf("%d%d", &n, &m);
	if(n>m) swap(n, m);
	if(n==1){
		ans=1;
		for(int i=1; i<=m; ++i) ans=ans*2%P;
		return printf("%d", ans), 0;
	}
	if(n==2){
		ans=4;
		for(int i=1; i<m; ++i) ans=ans*3ll%P;
		return printf("%d", ans), 0;
	}

	// init
	f[n+m+1]=1;
	for(int i=n+m; i>=4; --i) f[i]=(ll)f[i+1]*(a[i]=2+(i<=n+1)+(i<=m+1))%P;
	// 1 & 2
	ans=4*(f[4]+(ll)(a[5]+1)*f[6])%P;
	// 3
	for(int i=5; i<=n+1; ++i){
		int x=2+(i<=m+1);
		ans=(ans+2ll*(1+x)*(a[i+1]+1)*f[i+2])%P;
	}
	ans=(ans+2ll*(a[n+2]+1)*f[n+3])%P;
	// 4
	for(int i=5; i<=m+1; ++i){
		int x=2+(i<=n+1);
		ans=(ans+2ll*(1+x)*(a[i+1]+1)*f[i+2])%P;
	}
	ans=(ans+2ll*(a[m+2]+1)*f[m+3])%P;

	printf("%d\n", ans);
	return 0;
}