[AdditionalFile5599.zip](file://AdditionalFile5599.zip?type=additional_file)

#5599. 「USACO 2026 Second Platinum」Cow Circle

标签: 传统 | 时间限制: 6000 ms | 内存限制: 512 MiB |

题目描述

题目译自 USACO 2026 Second Contest, Platinum Problem 2. Cow Circle

农夫约翰有 $N$（$1 \leq N \leq 5000$）头奶牛站在一个圆形跑道周围，跑道被分为 $M$（$1 \leq M \leq 10^6$）个等距的位置，顺时针编号为 $0$ 到 $M-1$。奶牛 $i$ 最初位于位置 $x_i$，满足 $0 = x_1 < x_2 < \dots < x_N < M$。

对于每一头奶牛 $i$（$1 \leq i \leq N$），她将以该奶牛特定的概率独立且随机地选择面向顺时针方向或逆时针方向。一旦奶牛选定了初始方向，她就会以每分钟一个位置的恒定速度沿该方向持续移动。每当两头奶牛相遇（即占据相同的位置）时，她们会彼此反弹：立即反转方向并以相同的速度沿新方向继续移动。

农夫约翰想知道奶牛 $1$ 最终会停在哪里。对于每个 $0 \leq i < M$，求 $K$（$1 \leq K \leq 10^{18}$）分钟后奶牛 $1$ 位于位置 $i$ 的概率。

输入格式

第一行包含 $T$（$1 \leq T \leq 100$），即测试用例的数量。每个测试用例的格式如下：

每个测试用例的第一行包含 $N$（$1 \leq N \leq 5000$），$M$（$1 \leq M \leq 10^6$）和 $K$（$1 \leq K \leq 10^{18}$）。

第二行包含 $N$ 个整数 $p_1, \dots, p_N$（$0 \leq p_i < 10^9 + 7$），其中如果 $\frac{a_i}{b_i}$ 是奶牛 $i$ 选择顺时针方向的概率，那么 $p_i \cdot b_i \equiv a_i \pmod{10^9+7}$。

第三行也是最后一行包含 $N$ 个整数 $x_1, x_2, \dots, x_N$。

保证所有测试用例中 $N^2$ 的总和 $\leq 5000^2$，所有测试用例中 $M$ 的总和 $\leq 10^6$。

输出格式

为每个测试用例输出新的一行。每行的格式应如下：

对于每个 $0 \leq i < M$，设 $\frac{p_i}{q_i}$ 为 $K$ 分钟结束时奶牛 $1$ 位于位置 $i$ 的概率。输出 $M$ 个空格分隔的整数，即 $p_iq_i^{-1} \pmod{10^9 + 7}$（其中 $p_iq_i^{-1} \cdot q_i \equiv p_i \pmod{10^9+7}$）。

样例

输入

3
2 2 1
500000004 500000004 
0 1
3 3 1
500000004 500000004 500000004
0 1 2
5 10 13
500000004 1 500000004 0 500000004
0 3 4 7 9

输出

500000004 500000004
500000004 250000002 250000002
0 0 0 125000001 375000003 0 125000001 375000003 0 0

对于第一个测试用例，两头奶牛都有 $\frac{1}{2}$ 的概率选择任意方向。如果她们选择相同的方向，她们最终会交换位置（所以奶牛 $1$ 最终在 $1$）。否则，她们会在中间反弹并回到各自的初始位置。因此，奶牛 $1$ 最终在 $0$ 的概率为 $\frac{1}{2}$，最终在 $1$ 的概率也为 $\frac{1}{2}$。

对于第二个测试用例，所有奶牛再次拥有 $\frac{1}{2}$ 的概率选择任意方向。对于每种方向组合，奶牛 $1$ 的最终位置如下（CW 代表顺时针，CCW 代表逆时针）：

• CW, CW, CW: $1$
• CW, CW, CCW: $1$
• CCW, CCW, CCW: $2$
• CCW, CW, CCW: $2$
• CW, CCW, CW: $0$
• CW, CCW, CCW: $0$
• CCW, CW, CW: $0$
• CCW, CCW, CW: $0$

数据范围与提示

• 测试点 2：$K \leq 100, N \leq 10$
• 测试点 3：$N \leq 10$
• 测试点 4-7：$\sum N^3 \leq 500^3$
• 测试点 8-11：$K < \frac{M}{2}$
• 测试点 12-15：无额外约束

供题：Sujay Konda