| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
There is a graph with n nodes.The edges are generated with different probabilities.
P[i][j] is the probability of generating the edge i->j .
For every i, you want to know the probability that the first node can go to the i-th node through the generated edges .
n<=80
I don't know how to solve it ,can you help me?
Auto comment: topic has been updated by Gary2005 (previous revision, new revision, compare).
Divide the vertices in two set A,B each having $$$\dfrac{n}{2}$$$ vertices. For each Set, you separetely calculate the answer, let $$$f(S)$$$ return the probability matrix for vertices in $$$S$$$.
Now, to combine the answer, you can iterate over the path $$$a\rightarrow b\rightarrow c\rightarrow d$$$ where $$$a,b,c,d \in A,B$$$ and not all of them belong in the same set. This will be $$$f(A)[a][b] \times P[b][c] \times f(B)[c][d]$$$.
The overall complexity should be $$$\mathcal{O}(n^4\log n)$$$
I don't think it is right:
For example ,$$$a,b,d\in A$$$and $$$c\in B$$$,you can also go through this path a->b->c->d .
Hmm, You're right. We can add that case also.
For the tuple $$$(a,b,c,d)$$$ we can find all cases such that each vertex is in $$$A$$$ or $$$B$$$ and not all of them belong in the same set. There are $$$14$$$ such cases, so the overall complexity still holds.
Thanks for pointing that out though. Updated.
But how to deal with this case:
a->b->c->d->e->f->g ,where (a,c,e,g $$$\in A$$$,others $$$\in B$$$)
I think Gaussian elimination will be helpful here
https://codeforces.me/blog/entry/60003
See the Markov chain and cyclic expected value.
I have ever thought of this.But it can't work
Here it is mentioned that exact probability cannot be solved in polynomial time.
https://math.stackexchange.com/questions/1678084/probability-u-v-are-connected-in-a-random-graph-model
But you can calculate upper bound and lower bound on probability
Bruh this is amazing. There are many problems of cyclic expected value(I didn't know they were called as such) that I have solved with an equation system but don't know why the solution is correct. Gonna go read about them brb. Thank you!