BZOJ4005

BZOJ4005[LJOI2015]骗我呢

给你一个 \(n \times m\) 的矩阵, 求满足下列条件的方案数 \(n, m \le 10 ^ 6\) \[ x_{i,j} \in [0,m] \\ x_{i,j} < x_{i, j + 1} \\ x_{i, j} < x_{i - 1, j + 1} \]

暴力DP

因为要求每行一定严格单增

所以每行一定只会有一个 \([0,m]\) 区间内的数没有填

所以设 \(f[i][j]\) 表示考虑了前 \(i\) 行, 第 \(i\) 行中 \(j\) 这个数没有填的总方案数

有转移 \[ f[i][j] = \sum _ {k = 0} ^ {j + 1} f[i - 1][k] \] 前缀和优化一下 \[ f[i][j] = f[i][j - 1] + f[i - 1][j + 1] \] 以上只针对 \(i \ge 1 \ \ and \ \ j < m\) 的情况

我们可以张画图看看

这是一个 \(2 \times 2\) 的矩阵, 看起来不太方便, 我们可以平移一下

最后就是要求到 \(A, B, C\) 点的方案数的总和, 那么这样还要求和, 好麻烦啊, 那我们就再加一列

那么问题就变成了求到 \(L\) 点的方案数了, 这样还是不太好看啊, 我们旋转 \(180\)

发现我们要求的就是从原点出发只能向上或向右走, 并且不能接触到 \(NM, PO\) 直线, 走到 \(L(n + m + 1, n)\) 的总方案数

为了后文好描述, 我们记 \(MN = A : y = x + 1, PO = B : y = x - (m + 2)\)

我们考虑从原点出发走到一个点 \((x, y)\) 的总方案数显然是 \(\binom{x + y}{x}\)

那么考虑从原点到 \(L\) 点的方案数可以是总方案数减去不合法的方案数

不合法的方案数肯定会穿越 \(A \ \ or \ \ B\) 直线, 那么穿越直线的情况为这样的一个形式\(ABAAABAB \cdots\)

可能会有很多, 我们考虑缩一下, 把反复穿越同一条直线之间的情况缩起来, 变成 \(ABABA\cdots\) 的形式

其实就是要我们考虑第一次穿过 \(A\) 的方案数, 和第一次穿过 \(B\) 的方案数, 最终用总方案数减去这两种就是答案了

首先我们设终点为 \(L(x,y)\) 而其关于 \(A\) 对称的点为 \(L'(x', y')\)

考虑从原点走到 \(L'(x',y')\) 的路径都是以 \(A\)\(AB\) 的结尾的, 也就是最后穿过两条直线的顺序是 \(A\)\(AB\), 减掉这个方案

然后把 $ L'(x',y') $ 沿着 \(B\) 对称, 得到 \(L''(x'',y'')\) , 再把这个方案数加回去, 就是以 \(BA\)\(BAB\) 结尾的方案数, 然后这样反复进行下去, 直到 \(x < 0 \ \ or \ \ y < 0\)

然后这样我们到底得到了什么呢? 对, 我们减去了以 \(A\) 开头的总方案数

那么关于 \(B\) 开头的方案数就先沿着 \(B\) 对称就好了

太妙了 \(Orz\) 出题人