AGC018E

技术文章 1年前 (2020) 完美者
1,467 0

标签:路径   枚举   矩形   不难   span   cal   str   sum   har   

AGC018E [* hard]

给你三个矩形。

三个矩形从左下到右上排开。矩形顶点坐标范围是1e6

\(X,Y\) 依次升序排序。

在三个矩形内先分别选一个点出来,构成 S, T, P,求从 S 走到 T 走到 P 的方案数。

对于所有选点方案,求和。

\(X,Y\le 10^6\)

\(\rm Sol:\)

稍微看了一下下题解,感觉非常仙。

点到点的方案数

\(\binom{x+y}{x}\)

枚举点,\(\mathcal O(N^6)\)

点到矩形的方案数

即:

\[\begin{aligned} &\sum_{j=y_1}^{y_2}\sum_{i=x_1}^{x_2} \binom{i+j}{j} \\&=\sum_{j=y_1}^{y_2}\sum_{k=x_1+j}^{x_2+j} \binom{k}{j} \\&=\sum_{j=y_1}^{y_2} \bigg( \binom{x_2+j+1}{j+1}-\binom{x_1+j}{j+1}\bigg ) \\&=\sum_{j=y_1}^{y_2}\binom{x_2+j+1}{x_2}-\sum_{j=y_1}^{y_2} \binom{x_1+j}{x_1-1} \\&=\binom{x_2+y_2+2}{x_2+1}-\binom{x_2+y_1+1}{x_2+1}-\binom{x_1+y_2+1}{x_1}-\binom{x_1+y_1}{x_1} \end{aligned}\]

不难发现点走到矩形的方案数等同于点走到 \((x_2+1,y_2+1),(x_2+1,y_1),(x_1,y_2+1),(x_1,y_1)\) 的方案数之差。

枚举 S 和 T,复杂度为 \(\mathcal O(N^4)\)

枚举 T,然后分别算,复杂度为 \(\mathcal O(N^2)\)

矩形到矩形

注意到对于第一个矩形的每个点现在等同于 \(4\) 的点的差分的组合,于是我们只需要考虑那 \(4\) 个点走到矩形的方案数,大概是可以通过 \(16\) 个点来表示答案。

从矩形出发,经过矩形,到达另一个矩形

等价于从这 \(16\) 个点出发,且路径经过了那个矩形的方案数。

注意到进入点是 \(\mathcal O(N)\) 的,所以枚举进入点即可。

复杂度 \(\mathcal O(16N)\)

本题

然而在第二个矩形中走的路径长度会影响答案。

假设走的长度为 \(\rm len\),那么对答案的贡献为 \(\rm len\)

假设从 \((x_1,y_1)\) 进入,从 \((x_2,y_2)\) 出去,那么对答案的贡献是 \((x_2+y_2)-(x_1+y_1)\)

等一下,好像维度可以分离?!

枚举进入点,枚举出去点,分别算贡献即可,复杂度 \(\mathcal O(16\times 4\times n)\),大概是 \(\mathcal O(64n)\)

AGC018E

标签:路径   枚举   矩形   不难   span   cal   str   sum   har   

原文地址:https://www.cnblogs.com/Soulist/p/13653643.html

版权声明:完美者 发表于 2020-09-17 22:21:09。
转载请注明:AGC018E | 完美导航

暂无评论

暂无评论...