Cow Circle
플래티넘 II의견: 0
*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.
Problem credits: Sujay Konda
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.
Problem credits: Sujay Konda
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}\)).
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 9500000004 500000004
500000004 250000002 250000002
0 0 0 125000001 375000003 0 125000001 375000003 0 0For 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\)
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Platinum
평가 및 의견
Cow Circle
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cow Circle