考虑容斥，拆成四部分，每部分都形如

\[\sum_{i=0}^n\sum_{j=0}^mf(i,j) \]

其中 \(f(i,j)\) 表示从 \((0,0)\) 走到 \((i,j)\) 的方案数，显然为 \(\dbinom{i+j}{i}\)。

而

\[\sum_{j=0}^m f(i,j)=f(i+1,m) \]

这个东西放到坐标系上很直观，每条走到 \((i+1,m)\) 的路径都可以被划分成某条走到 \((i,j)\) 的路径，然后向右走一步，之后一直向上走到 \((i+1,m)\)。

同理

\[\sum_{i=0}^nf(i,j)=f(n,j+1) \]

因此

\[\sum_{i=0}^n\sum_{j=0}^mf(i,j)=\sum_{i=0}^nf(i+1,m) \]

\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n+1}f(i,m) \]

\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =f(n+1,m+1)-f(0,m+1) \]

\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =f(n+1,m+1)-1 \]

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2000005, mod = 1e9 + 7;
int l1, r1, l2, r2;
int fac[N], inv[N];

int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return res;
}

void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2);
	for (int i = n - 1; ~i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

int C(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}

int f(int x, int y) {
	return C(x + y, x);
}

int solve(int x, int y) {
	return (f(x + 1, y + 1) - 1 + mod) % mod;
}

void add(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
}

void sub(int &a, int b) {
	a -= b;
	if (a < 0) a += mod;
}

int main() {
	init(N - 1);
	scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
	int ans;
	add(ans, solve(l2, r2)), sub(ans, solve(l1 - 1, r2)), sub(ans, solve(l2, r1 - 1)), add(ans, solve(l1 - 1, r1 - 1));
	printf("%d", ans);
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16879474.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性