「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;
}