Description：

三个矩形从左下到右上排开。矩形顶点坐标范围是 $10^6$ ，求在三个矩形中各选一个点经过这三个点从第一个点到第三个点的最短路条数。

$1\leqslant X_1\leqslant X_2<X_3\leqslant X_4<X_5\leqslant X_6\leqslant 10^6$

Solution：

首先设 $C(x,y)$ 表示从 $(0,0)$ 沿最短路走到 $(x,y)$ 的方案数，显然 $C(x,y)=C^{x+y}_x$ ，但是还有一个性质，就是： $$ C(x,y)=\sum_{i=0}^yC(x-1,i) $$ 也就是说先走到 $x$ 下面一行，然后向上走一步，再一直向右走到 $y$ ，显然是不重不漏的，推广一下： $$ \begin{align} C(x,y)&=\sum_{j=0}^yC(x-1,j)\\ &=\sum_{j=1}^yC(x-1,j)+C(x-1,0)\\ &=\sum_{j=1}^yC(x-1,j)+1\\ &=\sum_{j=0}^{y-1}\sum_{i=0}^{x-1}C(i,j)+1\\ \end{align} $$ 即： $$ \sum_{x=0}^X\sum_{y=0}^YC(x,y)=C(X+1,Y+1)-1 $$ 也就是说： $$ \sum_{x=X_1}^{X_2}\sum_{y=Y_1}^{Y_2}C(x,y)=C(X_2+1,Y_2+1)−C(X_2+1,Y_1)−C(X_1,Y_2+1)+C(X_1,Y_1) $$ 也就是说从第一个矩形到第三个矩形的所有路径都可以通过从第一个矩形的所有点到第三个矩形的四个点来计算，这个时候我们可以换个思维，可以把这个看成从第三个矩形的四个点到第一个矩形的所有点，于是又可以运用上面那个公式，这样计算的复杂度就变成了 $4\times 4$ ，最后再考虑二号矩形的贡献，会发现是原来的每个方案乘上经过第二个矩形的长度，那么我们可以枚举第二个矩形的进入点 $(x_1,y_1)$ ，离开点 $(x_2,y_2)$ ，那么 $len=x_2-x_1+y_2-y_1+1$ ，发现这四项其实都可以分离，也就是说我们可以先枚举进入点 $(x_1,y_1)$ ，然后给答案累加 $(-1)\times$ 两个组合数 $\times (x_1+y_1)$ ，再枚举离开点 $(x_2,y_2)$ ，给答案累加 $(+1)\times$ 两个组合数 $\times(x_2+y_2+1)$ ，发现每个合法路径被统计了两次，第一次计算了 $(-1)\times (x_1+y_1)$ ，第二次 $(+1)\times(x_2+y_2+1)$ ，刚好是 $len$ 次，由于进入点和离开点都只有 $O(n)$ 个，所以时间复杂度被成功优化到了 $O(\max(x_2,y_2))\times 16$ 。注意这里的枚举进入点并不是枚举点，而是枚举从哪个方向进入了这个点，也就是说对于左下角的和右上角的点，从两个方向进去是不同的，要枚举这个进去的方向。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cctype>

#include<cstring>

using namespace std;

struct rec

{

	int x1,x2,y1,y2;

}s1,s2,s3;

#define MAXN 2000010

#define MOD 1000000007

int fac[MAXN],inv[MAXN];

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int comb(int n,int m)

{

	return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

int C(int x1,int y1,int x2,int y2)

{

	if(x1 > x2)swap(x1,x2);if(y1 > y2)swap(y1,y2);

	return comb(y2 - y1 + x2 - x1,y2 - y1);

}

int calc(int x,int y,rec s)

{

	if(x >= s.x1 && x >= s.x2 && y >= s.y1 && y >= s.y2)

	{

		s.x1 *= -1;s.y1 *= -1;s.x2 *= -1;s.y2 *= -1;

		swap(s.x1,s.x2);swap(s.y1,s.y2);

		x *= -1;y *= -1;

	}

	int ans = 0;

	ans = (ans + C(x,y,s.x2 + 1,s.y2 + 1)) % MOD;

	ans = (ans - C(x,y,s.x2 + 1,s.y1) + MOD) % MOD;

	ans = (ans - C(x,y,s.x1,s.y2 + 1) + MOD) % MOD;

	ans = (ans + C(x,y,s.x1,s.y1)) % MOD;

	return ans;

}

int main()

{

	fac[0] = 1;for(int i = 1;i < MAXN;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	inv[MAXN - 1] = power(fac[MAXN - 1],MOD - 2);

	for(int i = MAXN - 2;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

	scanf("%d%d%d%d%d%d",&s1.x1,&s1.x2,&s2.x1,&s2.x2,&s3.x1,&s3.x2);

	scanf("%d%d%d%d%d%d",&s1.y1,&s1.y2,&s2.y1,&s2.y2,&s3.y1,&s3.y2);

	int ans = 0;

	for(int i = s2.x1;i <= s2.x2;++i)

	{

		ans = (ans - 1ll * calc(i,s2.y1 - 1,s1) * calc(i,s2.y1,s3) % MOD * (i + s2.y1) % MOD + MOD) % MOD;

		ans = (ans + 1ll * calc(i,s2.y2,s1) * calc(i,s2.y2 + 1,s3) % MOD * (i + s2.y2 + 1) % MOD) % MOD;

	}

	for(int i = s2.y1;i <= s2.y2;++i)

	{

		ans = (ans - 1ll * calc(s2.x1 - 1,i,s1) * calc(s2.x1,i,s3) % MOD * (s2.x1 + i) % MOD + MOD) % MOD;

		ans = (ans + 1ll * calc(s2.x2,i,s1) * calc(s2.x2 + 1,i,s3) % MOD * (s2.x2 + i + 1) % MOD) % MOD;

	}

	cout << ans << endl;

	return 0;

}