AGC018E Sightseeing Plan <组合数学>

Posted on 2018-10-02 Symbols count in article: 1.6k Reading time ≈ 6 mins.

Problem

Sightseeing Plan

$\mathrm{Time\;limit:\;8\;Sec}$
$\mathrm{Memory\;limit:\;256\;MB}$

Statement

Joisino is planning on touring Takahashi Town. The town is divided into square sections by north-south and east-west lines. We will refer to the section that is the $x^{th}$ from the west and the $y^{th}$ from the north as $(x,y)$ .
Joisino thinks that a touring plan is good if it satisfies the following conditions:
Let $(p,q)$ be the section where she starts the tour. Then, $X_1\le p\le X_2$ and $Y_1\le q\le Y_2$ hold.
Let $(s,t)$ be the section where she has lunch. Then, $X_3\le s\le X_4$ and $Y_3\le t\le Y_4$ hold.
Let $(u,v)$ be the section where she ends the tour. Then, $X_5\le u\le X_6$ and $Y_5\le v\le Y_6$ hold.
By repeatedly moving to the adjacent section (sharing a side), she travels from the starting section to the ending section in the shortest distance, passing the lunch section on the way.
Two touring plans are considered different if at least one of the following is different: the starting section, the lunch section, the ending section, and the sections that are visited on the way. Joisino would like to know how many different good touring plans there are. Find the number of the different good touring plans. Since it may be extremely large, find the count modulo $10^9+7$ .

Constraints

$1\le X_1\le X_2<X_3\le X_4<X_5\le X_6\le 10^6$
$1\le Y_1\le Y_2<Y_3\le Y_4<Y_5\le Y_6\le 10^6$

Input

Input is given from Standard Input in the following format:

\begin{matrix} X_1&X_2&X_3&X_4&X_5&X_6\\ Y_1&Y_2&Y_3&Y_4&Y_5&Y_6\\ \end{matrix}

Output

Print the number of the different good touring plans, modulo $10^9+7$ .

Sample

Input #1

1 2	1 1 2 2 3 4 1 1 2 2 3 3

Output #1

Explanation #1
The starting section will always be $(1,1)$ , and the lunch section will always be $(2,2)$ . There are four good touring plans where $(3,3)$ is the ending section, and six good touring plans where $(4,3)$ is the ending section. Therefore, the answer is $6+4=10$ .
Input #2

1 2	1 2 3 4 5 6 1 2 3 4 5 6

Output #2

Input #3

1 2	77523 89555 420588 604360 845669 973451 2743 188053 544330 647651 709337 988194

Output #3

137477680

标签：组合数学

Translation

给出三个矩形 $A:(X_1,Y_1)\sim(X_2,Y_2)$ ， $B:(X_3,Y_3)\sim(X_4,Y_4)$ ， $C:(X_5,Y_5)\sim(X_6,Y_6)$ 。
求从 $A$ 中任意一点出发，经过 $B$ 中任意指定一点，到达 $C$ 中任意一点，且只能向上走或向右走的路径数。
注意：如果两条路径相同，而在 $B$ 中经过的指定点不同，则视为两条不同路径。即，可将一条路径看成二元组 $(path,P)$ ，其中 $P$ 是在 $B$ 中指定经过的点，若两者中任意一者不同，则视为两条不同路径。

Solution

挺麻烦的计数。

设 $F(x,y)$ 为从 $(0,0)$ 走到 $(x,y)$ 的方案数，那么有 $F(x,y)=\frac{(x+y)!}{x!y!}$ 。
引理 1： $\sum_{y=0}^{Y}F(X,y)=F(X+1,Y)$ 。
证明：考虑所有从 $(0,0)$ 到 $(X+1,Y)$ 的路径，其一定经过其仅经过一条形如 $(X,i)\to(X+1,i)$ 的边。而经过 $(X,i)\to(X+1,i)$ 的路径的条数恰好为 $F(X,i)$ ，于是有 $\sum_{y=0}^{Y}F(X,y)=F(X+1,Y)$ 。
引理 2： $\sum_{x=0}^{X}\sum_{y=0}^{Y}F(x,y)=F(X+1,Y+1)-1$
证明：

\begin{aligned} \sum_{x=0}^{X}\sum_{y=0}^{Y}F(x,y) &=\sum_{x=0}^{X}F(x+1,Y)\\ &=-F(0,Y)+\sum_{x=0}^{X+1}F(x,Y)\\ &=F(X+1,Y+1)-1 \end{aligned}

由以上可用类似二维前缀和的方法得到

\sum_{x=X_1}^{X_2}\sum_{y=Y_1}^{Y_2}F(x,y)=F(X_1,Y_1)-F(X_1,Y_2+1)-F(X_2+1,Y_1)+F(X_2+1,Y_2+1)

于是我们有了一个计算从 $(0,0)$ 到一个矩形中的任意点的路径个数。类似地， $4\times4$ 枚举两个矩形各四个基准点即可对于任意在两个矩形中间的点 $(x,y)$ 计算从 $A$ 到其再到 $B$ 的路径条数。

对于一条路径，其一定进入 $B$ 一次再从 $B$ 出去一次，设入口和出口曼哈顿距离为 $dis$ ，则其一定能对应 $dis+1$ 条 $B$ 中指定点不同的路径。而从左边和下边的每个点进入于从上边和右边的每个点出去的贡献都是可以拆开的，于是枚举入点计算贡献，再枚举出点计算贡献。
具体地，

对于 $X_3\le x\le X_4$ ，从 $(x,Y_3)$ 进入的路径每条路贡献均为 $-(x+Y_3)$
对于 $Y_3\le y\le Y_4$ ，从 $(X_3,y)$ 进入的路径每条路贡献均为 $-(X_3+y)$
对于 $X_3\le x\le X_4$ ，从 $(x,Y_4)$ 出去的路径每条路贡献均为 $x+Y_4+1$
对于 $Y_3\le y\le Y_4$ ，从 $(X_4,y)$ 出去的路径每条路贡献均为 $X_4+y+1$

附上官方题解

Code

#include <bits/stdc++.h>
#define MX 2000000
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt fac[MX+5], inv[MX+5];
int X1, X2, X3, X4, X5, X6;
int Y1, Y2, Y3, Y4, Y5, Y6;
void init() {
    fac[0] = inv[0] = inv[1] = 1;
    for (int i = 1; i <= MX; i++) fac[i] = fac[i-1]*i%P;
    for (int i = 2; i <= MX; i++) inv[i] = (P-P/i*inv[P%i]%P)%P;
    for (int i = 2; i <= MX; i++) inv[i] = inv[i]*inv[i-1]%P;
}
lnt F(int n, int m) {return fac[n+m]*inv[n]%P*inv[m]%P;}
lnt calc(int sx, int sy, int tx, int ty) {
    lnt ret = 0;
    for (int x = X3, y = Y3; x <= X4; x++)
        ret = (ret+1LL*(P-x-y)*F(x-sx, y-sy-1)%P*F(tx-x, ty-y)%P)%P;
    for (int x = X3, y = Y3; y <= Y4; y++)
        ret = (ret+1LL*(P-x-y)*F(x-sx-1, y-sy)%P*F(tx-x, ty-y)%P)%P;
    for (int x = X3, y = Y4; x <= X4; x++)
        ret = (ret+1LL*(x+y+1)*F(x-sx, y-sy)%P*F(tx-x, ty-y-1)%P)%P;
    for (int x = X4, y = Y3; y <= Y4; y++)
        ret = (ret+1LL*(x+y+1)*F(x-sx, y-sy)%P*F(tx-x-1, ty-y)%P)%P;
    return ret;
}
int main() {
    init(); lnt ans = 0;
    read(X1), read(X2), read(X3), read(X4), read(X5), read(X6);
    read(Y1), read(Y2), read(Y3), read(Y4), read(Y5), read(Y6);
    ans = (ans+calc(X1-1, Y1-1, X5, Y5))%P;
    ans = (ans+calc(X1-1, Y1-1, X6+1, Y6+1))%P;
    ans = (ans-calc(X1-1, Y1-1, X5, Y6+1)+P)%P;
    ans = (ans-calc(X1-1, Y1-1, X6+1, Y5)+P)%P;
    ans = (ans+calc(X2, Y2, X5, Y5))%P;
    ans = (ans+calc(X2, Y2, X6+1, Y6+1))%P;
    ans = (ans-calc(X2, Y2, X5, Y6+1)+P)%P;
    ans = (ans-calc(X2, Y2, X6+1, Y5)+P)%P;
    ans = (ans-calc(X1-1, Y2, X5, Y5)+P)%P;
    ans = (ans-calc(X1-1, Y2, X6+1, Y6+1)+P)%P;
    ans = (ans+calc(X1-1, Y2, X5, Y6+1))%P;
    ans = (ans+calc(X1-1, Y2, X6+1, Y5))%P;
    ans = (ans-calc(X2, Y1-1, X5, Y5)+P)%P;
    ans = (ans-calc(X2, Y1-1, X6+1, Y6+1)+P)%P;
    ans = (ans+calc(X2, Y1-1, X5, Y6+1))%P;
    ans = (ans+calc(X2, Y1-1, X6+1, Y5))%P;
    return printf("%lld\n", ans), 0;
}