[日常训练] 藏宝路径

路径"/>

[日常训练] 藏宝路径

【问题描述】

经过你的帮助，小Y终于得到了藏宝图。
藏宝图是一个m*n的网格。宝藏分散在(m,n)、 (m,q)两个地方。小Y、小Z分别在(0,0)、(p,0)两个位置，他们决定每个人去一个地方找宝藏。小Y去(m,n)地，小Z去(m,q)地，其中，p &lt; &lt; <m，q &lt; &lt; <n。小Y和小Z只能沿着坐标系中整数组成的网格向x轴或者y轴的正方向爬行。
小Y想知道，在两人所走的路径不重叠（两条路径没有相交的地方）的情况有多少种？

【输入格式】

输入一行，依次为m、n、p、q，都是小于100000的正整数。
###【输出格式】
输出一行一个数，表示所有情况的数量 模(mod) 质数100,000,007的结果。

【输入输出样例】

path.in
3 2 1 1

path.out
6

【样例说明】

当小Y走 ( 0 , 0 ) → ( 0 , 2 ) → ( 3 , 2 ) (0,0) \to (0,2) \to (3,2) (0,0)→(0,2)→(3,2)时，小Z有3种走法： ( 1 , 0 ) → ( 1 , 1 ) → ( 3 , 1 ) (1,0) \to (1,1) \to (3,1) (1,0)→(1,1)→(3,1) ( 1 , 0 ) → ( 2 , 0 ) → ( 2 , 1 ) → ( 3 , 1 ) (1,0) \to (2,0) \to (2,1) \to (3,1) (1,0)→(2,0)→(2,1)→(3,1) ( 1 , 0 ) → ( 3 , 0 ) → ( 3 , 1 ) (1,0) \to (3,0) \to (3,1) (1,0)→(3,0)→(3,1)类似的：
小Y还可以走 ( 0 , 0 ) → ( 0 , 1 ) → ( 1 , 1 ) → ( 1 , 2 ) → ( 3 , 2 ) (0,0) \to (0,1) \to (1,1) \to (1,2) \to (3,2) (0,0)→(0,1)→(1,1)→(1,2)→(3,2)，此时小Z有2种走法。
小Y还可以走 ( 0 , 0 ) → ( 0 , 1 ) → ( 2 , 1 ) → ( 2 , 2 ) → ( 3 , 2 ) (0,0) \to (0,1) \to (2,1) \to (2,2) \to (3,2) (0,0)→(0,1)→(2,1)→(2,2)→(3,2)，此时小Z有1种走法。
所以，共6种。

【数据规模】

对于20%的数据，m+n小于10。
对于50%的数据，m+n小于20。
对于70%的数据，m+n小于20000。
对于100%的数据，m+n小于200000。

【分析】组合数学 + 费马小定理

• 首先我们不考虑路径相交的问题，则从 ( 0 , 0 ) (0, 0) (0,0)走到 ( m , n ) (m, n) (m,n)共有 C m + n n C_{m + n}^n Cm+nn​或 C m + n m C_{m + n}^m Cm+nm​条路径（两者等价，表示共走 m + n m + n m+n步，选择 n n n步向上走或选择 m m m步向右走的方案数）
• 接下来我们先算出总的路径数，再减去不合法的相交路径数
• 一种不合法的相交路径如下图
  
• 实际上也就相当于分为从 ( 0 , 0 ) (0, 0) (0,0)到 ( m , q ) (m, q) (m,q)和从 ( p , 0 ) (p, 0) (p,0)到 ( m , n ) (m, n) (m,n)两条路径，如下图
  
• 则最后的答案为
  C m + n n × C m − p + q q − C m + q q × C m − p + n n C_{m + n}^n \times C_{m - p + q}^q - C_{m + q}^q \times C_{m - p + n}^n Cm+nn​×Cm−p+qq​−Cm+qq​×Cm−p+nn​
• 但这里计算组合数 C C C要用到除法，而我们又要对其取模，则又要引出一个概念：费马小定理
• 设模数为 p p p（要求为素数），则 1 a ( m o d &ThinSpace;&ThinSpace; p ) = a p − 2 ( m o d &ThinSpace;&ThinSpace; p ) \frac{1}{a} (\mod\ p) = a^{p - 2} (\mod\ p) a1​(mod p)=ap−2(mod p)
• 那么 C n m ( m o d &ThinSpace;&ThinSpace; p ) = n ! m ! × ( n − m ) ! ( m o d &ThinSpace;&ThinSpace; p ) C_n^m(\mod\ p) = \frac{n!} {m! \times (n - m)!} (\mod\ p) Cnm​(mod p)=m!×(n−m)!n!​(mod p) = n ! × ( m ! × ( n − m ) ! ) p − 2 ( m o d &ThinSpace;&ThinSpace; p ) = n! \times (m! \times (n - m)!)^{p - 2} (\mod\ p) =n!×(m!×(n−m)!)p−2(mod p)
• 我们就可以预处理出 x ! ( 0 ≤ x ≤ 200 , 000 ) x!(0 \le x \le 200,000) x!(0≤x≤200,000)，直接用快速幂计算答案即可

【代码】

#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;
typedef long long ll;
const ll Mod = 1e8 + 7; 
const int N = 2e5 + 5;
ll f[N]; int n, m, p, q;inline ll Pow(ll x, ll k)
{ll res = 1;while (k){if (k & 1) (res *= x) %= Mod;(x *= x) %= Mod; k >>= 1;}return res;
}inline ll C(const int n, const int m)
{return f[n] * Pow(f[m] * f[n - m] % Mod, Mod - 2) % Mod;
}int main()
{freopen("path.in", "r", stdin);freopen("path.out", "w", stdout);f[1] = f[0] = 1; scanf("%d%d%d%d", &m, &n, &p, &q);for (int i = 2; i <= n + m; ++i) f[i] = (f[i - 1] * i) % Mod;cout << (C(m + n, n) * C(m - p + q, q) % Mod - C(m + n - p, n) * C(m + q, q) % Mod + Mod) % Mod << endl;fclose(stdin); fclose(stdout);return 0;
}