题解 AT2674 【[AGC018E] Sightseeing Plan】

· · 题解

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/AGC018.html。

如果固定中转点。那么方案数就是每个起点到中转点，和每个终点到中转点，的方案数的乘积。

那么一个矩形的起点，到一个点，的方案数。其实就是杨辉三角上一个菱形的和。

其实就是四个点到一个点的方案数（但是系数是两个 +1 两个 -1）。

那么现在就转化成 4 \times 4 = 16 种情况的，起点和终点都是唯一的，但是中转点是在一个区域内的情况。

此时就相当于：对每个起点到终点的每条路径，把经过那个区域的长度求和。

此时又是一个很重要的转换：经过那个区域的长度转化成，离开那个区域时的坐标，减去进入那个区域时的坐标（曼哈顿距离）。

那么我们就可以枚举离开那个区域时的位置，求出满足的路径数，乘以曼哈顿坐标贡献给答案。

进入那个区域的情况同理。

预处理组合数，时间复杂度就是坐标范围。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 1000000007;
const int MV = 2000005;

inline int qPow(int b, int e) {
    int a = 1;
    for (; e; e >>= 1, b = (LL)b * b % Mod)
        if (e & 1) a = (LL)a * b % Mod;
    return a;
}
inline int gInv(int b) { return qPow(b, Mod - 2); }

int Fac[MV], iFac[MV];
inline void Init(int N) {
    Fac[0] = 1;
    for (int i = 1; i <= N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
    iFac[N] = gInv(Fac[N]);
    for (int i = N; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
}
inline int Binom(int N, int M) {
    if (M < 0 || M > N) return 0;
    return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;
}
inline int Calc(int N, int M) {
    return Binom(N + M, N);
}

int X1, X2, X3, X4, X5, X6;
int Y1, Y2, Y3, Y4, Y5, Y6;

int sx[4], sy[4], tx[4], ty[4];
int Ans;

int main() {
    Init(2000000);
    scanf("%d%d%d%d%d%d", &X1, &X2, &X3, &X4, &X5, &X6);
    scanf("%d%d%d%d%d%d", &Y1, &Y2, &Y3, &Y4, &Y5, &Y6);
    sx[0] = X1 - 1, sy[0] = Y1 - 1;
    sx[1] = X1 - 1, sy[1] = Y2;
    sx[2] = X2, sy[2] = Y2;
    sx[3] = X2, sy[3] = Y1 - 1;
    tx[0] = X6 + 1, ty[0] = Y6 + 1;
    tx[1] = X6 + 1, ty[1] = Y5;
    tx[2] = X5, ty[2] = Y5;
    tx[3] = X5, ty[3] = Y6 + 1;
    for (int sk = 0; sk < 4; ++sk) {
        for (int tk = 0; tk < 4; ++tk) {
            int spx = sx[sk], spy = sy[sk];
            int tpx = tx[tk], tpy = ty[tk];
            int coef = (sk ^ tk) & 1 ? -1 : 1;
            int Sum = 0;
            for (int i = X3; i <= X4; ++i) {
                Sum = (Sum + (LL)Calc(i - spx, Y3 - 1 - spy) * Calc(tpx - i, tpy - Y3) % Mod * -(i + Y3 - 1)) % Mod;
                Sum = (Sum + (LL)Calc(i - spx, Y4 - spy) * Calc(tpx - i, tpy - Y4 - 1) % Mod * (i + Y4)) % Mod;
            }
            for (int j = Y3; j <= Y4; ++j) {
                Sum = (Sum + (LL)Calc(X3 - 1 - spx, j - spy) * Calc(tpx - X3, tpy - j) % Mod * -(X3 - 1 + j)) % Mod;
                Sum = (Sum + (LL)Calc(X4 - spx, j - spy) * Calc(tpx - X4 - 1, tpy - j) % Mod * (X4 + j)) % Mod;
            }
            Ans = (Ans + coef * Sum) % Mod;
        }
    }
    printf("%d\n", (Ans + Mod) % Mod);
    return 0;
}