0%

「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)$ 为左上角的子矩阵斜线部分相同

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

再讨论

考虑这种情况

Initial

有 $5$ 种填法

0000, 0111 和 1111

0000001101111111

好像这四种都一样..

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

0001
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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}