Chro's Blog


同じ世界に、立っていたんだ。


「BZOJ 3782」上学路线

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. HINT
  7. 7. Solution

Description

小C所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。小C家住在西南角,学校在东北角。现在有T个路口进行施工,小C不能通过这些路口。小C喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小C又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小C只需要让你求出路径数mod P的值。

Input

第一行,四个整数N、M、T、P。

接下来的T行,每行两个整数,表示施工的路口的坐标。

Output

一行,一个整数,路径数mod P的值。

Sample Input

1
2
3
4
3 4 3 1019663265
3 0
1 1
2 2

Sample Output

1
8

HINT

1<=N,M<=10^10

0<=T<=200

p=1000003或p=1019663265

Solution

所有坏点加上终点放在一起排序(第一关键字 x,第二关键字 y),用 dp[i] 表示从起点走到第 i 个点有多少方案。

1019663265=3*5*6793*10007,套个中国剩余定理就行。

另外样例这么小是要闹哪样……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long maxt = 205;
const long maxn = 1000005;
const long modulo[5] = {3, 5, 6793, 10007, 1000003};
struct point {
long x, y;
bool operator<(const point &b) const {
if (x == b.x) return y < b.y;
return x < b.x;
}
} p[maxt];
long n, m, t, P, dp[maxt], mod;
long fac[maxn], finv[maxn];
long C(long n, long m) {
if (n < m || m < 0) return 0;
return fac[n] * finv[m] % mod * finv[n - m] % mod;
}
long lucas(long n, long m) {
if (n < m || m < 0) return 0;
if (n < mod && m < mod) return C(n, m);
return C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
}
long ways(long x, long y) { return lucas(x + y, x); }
void exgcd(long a, long b, long &x, long &y) {
if (b) exgcd(b, a % b, y, x), y -= x * (a / b);
else x = 1, y = 0;
}
long inv(long a) {
long x, y;
exgcd(a, mod, x, y);
return (x + mod) % mod;
}
long kase(long M) {
mod = M;
for (long i = fac[0] = 1; i < M; ++i) fac[i] = fac[i - 1] * i % M;
finv[M - 1] = inv(fac[M - 1]);
for (long i = M - 2; ~i; --i) finv[i] = finv[i + 1] * (i + 1) % M;
dp[0] = 0;
for (long i = 1; i <= t + 1; ++i) {
dp[i] = ways(p[i].x, p[i].y);
for (long j = 1; j < i; ++j) (dp[i] += M - dp[j] * ways(p[i].x - p[j].x, p[i].y - p[j].y) % M) %= M;
}
return dp[t + 1];
}
void CRT(long &a, long &p, long b, long q) {
long y, z;
exgcd(p, q, y, z);
y *= b - a;
a += p * y, p *= q;
((a %= p) += p) %= p;
}
long solve(long l, long r) {
long a = 0, p = 1, b;
for (long i = l; i <= r; ++i) {
b = kase(modulo[i]);
CRT(a, p, b, mod);
}
return a;
}
int main() {
scanf("%lld%lld%lld%lld", &n, &m, &t, &P);
for (long i = 1; i <= t; ++i) {
scanf("%lld%lld", &p[i].x, &p[i].y);
if (p[i].x < 0 || p[i].y < 0 || p[i].x > n || p[i].y > m) --i, --t;
}
p[t + 1] = (point){n, m};
sort(p + 1, p + t + 1);
printf("%lld\n", P == 1000003 ? solve(4, 4) : solve(0, 3));
return 0;
}
最近的文章

NOI 2017 -- AFO

终于到了这一天。NOI 2017。 这大概是我的最后一次 OI 竞赛了吧。写点东西纪念一下。 每日更新。不偷懒。 7.17上午到了绍兴……绍兴北站人真多…… 磨叽磨叽到了学校,11 点 40 了…… 想着要快点去吃饭,结果报到现场人更多……555555555 颓几局 popkart 刷了点模板,结束…

OI 继续阅读
更早的文章

「BZOJ 1815」「SHOI2006」color 有色图

Description Input输入三个整数N,M,P 1&lt; = N &lt;= 53 1&lt; = M &lt; = 1000 N&lt; P &lt; = 10^ 9 Output即总数模P后的余数 Sample Input13 2 97 Sample Output14 Solutio…

BZOJ, Polya 定理 继续阅读