题目
给定一个大小为(N × M)的矩形网格，每个格点用一个坐标((x, y))描述，这里满 足(1 ≤ x ≤ N)且(1 ≤ y ≤ M)。定义一个合法的路径同时满足如下条件：
（1） 路径的起点是((1,1))，终点是((N, M))；
（2） 到达一个点之后，只能往横坐标和纵坐标中有且仅有一个增加了(1)的点走。即((x, y))只能走到((x + 1, y))或((x, y + 1))；
（3） 满足(T)个限制，每个限制都形如：如果走到了((a, b))那么下一步一定要走到((c, d))。这里可能会有(a = N, b = M)的情况，不管就好了。 求有多少条合法的路径。
由于答案可能很大，请输出其对(10^9 + 7)取模的结果。
Solution
经过亲身被卡经历得出((c, d))的所有取值情况
((a, b))（a，b从一开始就不会被走进）
((a + 1, b))（右边的格将收不到左边的贡献）
((a, b + 1))（下面的格将收不到上面的贡献）
直接(nm)计算贡献，对于特殊点特殊处理就好了。
(mathrm{Code:})
#include <bits/stdc++.h>
const int mod = 1000000007;
const int N = 3010;
const int T = 1000010;
int n, m, t;
inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline void Add(int& a, int b) {
a = add(a, b);
return void();
}
int f[N][N], v[N][N];
inline int read() {
int s = 0, w = 1;
char c = getchar();
while ((c < '0' || c > '9') && c != '-') c = getchar();
if (c == '-') w = -1, c = getchar();
while (c <= '9' && c >= '0')
s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s * w;
}
template <class T>
inline void write(T x) {
if (x < 0) x = ~x + 1, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
return void();
}
signed main() {
// freopen("gugu.in", "r", stdin);
// freopen("gugu.out", "w", stdout);
n = read();
m = read();
t = read();
memset(v, 0, sizeof(v));
for (int i = 1; i <= t; ++i) {
int _a = read(), _b = read(), _c = read(), _d = read();
if (_c == _a + 1) v[_a][_b + 1] += 1;
if (_d == _b + 1) v[_a + 1][_b] += 2;
if (_c == _a && _b == _d) v[_a][_b + 1] += 1, v[_a + 1][_b] += 2;
}
f[1][1] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (i == 1 && j == 1) continue;
int tmp = 0;
if (v[i][j] == 1) Add(tmp, f[i - 1][j]);
if (v[i][j] == 2) Add(tmp, f[i][j - 1]);
if (v[i][j] == 0) Add(tmp, f[i][j - 1]), Add(tmp, f[i - 1][j]);
f[i][j] = tmp;
}
write(f[n][m]);
putchar(10);
return 0;
}
EX
其实我觉得这种题正式比赛中不会出现吧。
毕竟题意模棱两可完全考验理解的时候不会很多。
我是真的感到恶心。