Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


「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 定理 继续阅读