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