P15264 [USACO26JAN2] Cow Circle P

**Note: The time limit for this problem is 6s, thrice the default. The memory limit for this problem is 512MB, twice the default.**

Farmer John has $N$ ($1 \leq N \leq 5000$) cows standing around a circular track divided into $M$ ($1 \leq M \leq 10^6$) equally spaced positions, numbered $0$ to $M-1$ clockwise. Cow $i$ is initially at position $x_i$, where $0 = x_1 < x_2 < \dots < x_N < M$. For each $1 \leq i \leq N$, cow $i$ will independently and randomly choose either to face clockwise or counterclockwise with some probability specific to that cow. Once a cow has chosen her initial direction, she begins moving continuously in that direction at a constant speed of one position per minute. Whenever two cows meet (i.e., they occupy the same space), they bounce off of each other: immediately reversing their directions and continuing to move at the same speed in that direction. Farmer John is wondering where cow $1$ will end up. For each $0 \leq i < M$, find the probability that cow $1$ is at position $i$ after $K$ ($1 \leq K \leq 10^{18}$) minutes.

The first line contains $T$ ($1 \leq T \leq 100$), the number of independent test cases. Each test case is specified as follows: - The first line of each test case contains $N$ ($1 \leq N \leq 5000$), $M$ ($1 \leq M \leq 10^6$), and $K$ ($1 \leq K \leq 10^{18}$). - The second line contains $N$ integers $p_1, \dots, p_N$ ($0 \leq p_i < 10^9 + 7$) where if $\frac{a_i}{b_i}$ is the probability cow $i$ goes clockwise, then $p_i \cdot b_i \equiv a_i \pmod{10^9+7}$. - The third and final line contains $N$ integers $x_1, x_2, \dots, x_N$. It is guaranteed that the sum of $N^2$ over all test cases is $\leq 5000^2$ and the sum of $M$ over all testcases is $\leq 10^6$.

Output a new line for each test case. The line for each test case should be formatted as follows: - For every $0 \leq i < M$, let $\frac{p_i}{q_i}$ be the probability cow $1$ is in position $i$ at the end of $K$ minutes. Output $M$ space-separated integers $p_iq_i^{-1} \pmod{10^9 + 7}$ (where $p_iq_i^{-1} \cdot q_i \equiv p_i \pmod{10^9+7}$).

For the first test case, both cows have a $\frac{1}{2}$ chance of going in either direction. If both pick the same direction, they will end up swapping positions (so cow $1$ ends up at $1$). Otherwise, they will bounce off in the middle and return to their original positions. Therefore, there is a $\frac{1}{2}$ chance for cow $1$ to end up at $0$ and a $\frac{1}{2}$ chance for cow $1$ to end up at $1$. For the second test case, all cows again have a $\frac{1}{2}$ chance of going in either direction. For each combination of directions, here is where cow $1$ ends up at. - 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$ SCORING: - Input 2: $K \leq 100, N \leq 10$. - Input 3: $N \leq 10$. - Inputs 4-7: $\sum N^3 \leq 500^3$. - Inputs 8-11: $K < \frac{M}{2}$. - Inputs 12-15: No additional constraints.