레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 세 배인 6초이다. 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.*
농부 존은 \(M\) (\(1 \leq M \leq 10^6\))개의 같은 간격의 위치로 나누어진 원형 트랙 둘레에 서 있는 \(N\) (\(1 \leq N \leq 5000\))마리의 소를 가지고 있다. 위치는 시계 방향으로 \(0\)부터 \(M-1\)까지 번호가 매겨져 있다. 소 \(i\)는 처음에 위치 \(x_i\)에 있으며, \(0 = x_1 < x_2 < \dots < x_N < M\)이다.
각 \(1 \leq i \leq N\)에 대해, 소 \(i\)는 각자 고유한 확률에 따라 독립적으로 그리고 무작위로 시계 방향 또는 반시계 방향을 바라볼지 선택한다. 소가 초기 방향을 선택하고 나면, 분당 한 위치의 일정한 속도로 그 방향으로 계속 이동하기 시작한다. 두 소가 만나면(즉, 같은 지점을 차지하면) 서로 튕겨 나간다. 즉, 즉시 방향을 반대로 바꾸고 같은 속도로 그 방향으로 계속 이동한다.
농부 존은 소 \(1\)이 어디에 있게 될지 궁금하다. 각 \(0 \leq i < M\)에 대해, \(K\) (\(1 \leq K \leq 10^{18}\))분이 지난 후 소 \(1\)이 위치 \(i\)에 있을 확률을 구하시오.
문제 제공: Sujay Konda
채점 방식
- 입력 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
첫째 줄에 독립적인 테스트 케이스의 수 \(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\))이 주어지는데, 소 \(i\)가 시계 방향으로 갈 확률이 \(\frac{a_i}{b_i}\)라면 \(p_i \cdot b_i \equiv a_i \pmod{10^9+7}\)이다.
셋째이자 마지막 줄에 \(N\)개의 정수 \(x_1, x_2, \dots, x_N\)이 주어진다.
모든 테스트 케이스에 대한 \(N^2\)의 합은 \(5000^2\) 이하이고 \(M\)의 합은 \(10^6\) 이하임이 보장된다.
각 테스트 케이스마다 한 줄을 출력한다. 각 테스트 케이스에 대한 줄은 다음과 같은 형식이어야 한다.
모든 \(0 \leq i < M\)에 대해, \(K\)분이 지난 후 소 \(1\)이 위치 \(i\)에 있을 확률을 \(\frac{p_i}{q_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 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