33OJ
登录 注册

#P17702. [ICPC 2019 Nanjing R] Holes

    ID: 20154 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>递推2019概率论期望高斯消元ICPC南京

[ICPC 2019 Nanjing R] Holes

题目描述

给定一个 n×nn \times n 的棋盘,行和列均从 11 到 nn 编号。帅气少年 RDC 在指定位置打了若干个洞,其中第 ii 个洞位于 (xi,yi)(x_i, y_i)。

RDC 还养了一只名叫 PRD 的宠物猪排骨龙。现在,PRD 喝醉了,被留在了棋盘的格子 (r,c)(r, c) 上。它将会随机行走,每秒以等概率移动到一个相邻的格子。这里两个格子相邻当且仅当它们共享一条公共边。当 PRD 到达一个被打洞的格子时,它会掉进洞里并开始睡觉。

现在,RDC 想知道对于每个洞,他的宠物最终停留在该洞的期望耗时。

输入格式

第一行包含一个整数 TT (1≤T≤201 \leq T \leq 20),表示测试数据的组数。

对于每组测试数据,第一行包含两个整数 nn 和 kk (2≤n≤200,1≤k≤2002 \leq n \leq 200, 1 \leq k \leq 200),表示给定棋盘的大小和洞的数量。接下来 kk 行,第 ii 行包含两个整数 xix_i 和 yiy_i (1≤xi,yi≤n1 \leq x_i, y_i \leq n),表示第 ii 个洞的位置。每组测试数据的最后一行包含两个整数 rr 和 cc (1≤r,c≤n1 \leq r, c \leq n),意义如上所述。

我们保证 PRD 初始时不在任何一个洞上,且所有给定的洞互不相同。我们还保证至多只有一组测试数据满足 max⁡(n,k)>5\max(n, k) > 5。

输出格式

对于每组测试数据,在一行内按顺序输出到达每个洞的期望耗时(以秒计)。

更确切地说,如果一个洞是可达的,且期望耗时的既约分数为 pq\frac{p}{q},你应当输出最小的非负整数 rr 使得 q⋅r≡p(mod109+7)q \cdot r \equiv p \pmod{10^9+7}。你可以放心地假设在所有测试数据中这样的 rr 总是存在。如果一个洞是不可达的,则在对应的位置输出 GG。

2
3 3
1 1
1 2
2 1
2 2
5 3
5 3
4 1
3 2
4 5
GG 4 4
669185882 381533358 341349117

提示

翻译由 DeepSeek V4 Pro 完成