Competition
Practice
0 (0 votes)
Dynamic programming
Approved
Medium
Probability and statistics
Problem
86% Success 148 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Hasan is organizing a chess competition, there 2N participants, they are standing in a row and numbered from 1 to 2N from left to right.

There are N rounds, in the each round player number 1 in current row play against player number 2 in current row and player number 3 in current row play against player number 4 in current row and so on, the winner of each game advances to the next round, so the number of participants in round i (1-based) is 2N-i+1. all winners stand in a row in the next round in the same relative order as the current round.

the winner of last round is declared to be the winner of the competition.

Hasan has estimated the skills of the participants and now he know that if players i and j played against each other, then the probability that participant i win the game is Ai,j / 1000, of course Aj,i = 1000 - Ai,j, (for all i,j (i!=j) between 1 and 2N), the result of any game will never be draw.

Now Hasan wants to know the chances of each participant to be the winner, Help Hasan to compute the probability that participant i will be the winner for each i between 1 and 2N.

Let Pi be probability that i-th participant win, then find Pi * 10002N mod 109+7 for all i between 1 and 2N , it can be proven that Pi * 10002N is always integer.

Input:

First line contains integer N the next 2N lines each contains 2N integer numbers, the matrix A

Output:

print 2N space-separated integers in a single line, the i-th integer is Pi * 10002N mod 109+7

Constraints:

  • 1 <= N <= 10
  • 0 <= Ai,j <= 1000
  • Ai,i = 0

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
40 votes
Tags:
Dynamic ProgrammingException handlingApprovedMediumReadyOpenProbability and Statistics
Points:30
3 votes
Tags:
Dynamic ProgrammingMatrixProbability spacesAlgorithmsProbablityModular exponentiation
Points:30
3 votes
Tags:
MathematicsMediumOpenApprovedProbability and Statistics