Hi , I am interested to solve a problem and I can not find a polynomial solution . How many spanning trees are in a grid graph(N x M)?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.12.2024 07:56:49 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
If you're looking for an O((mn)O(1)) solution take a look at this.
Perhaps because of the special characteristics of the graph the determinant can be computed faster?
Can you explain the whole solution , please?
The answer for you question is the value of the determinant of the graph's Laplacian matrix. This matrix is computed multiplying the adjacency matrix by -1 and then adding the degree of each node on the main diagonal. Forgot to mention, after this you will have to erase the line and the column of an arbitrary vertex. You can consult this paper for proof. This will lead to a O((N * M)3) solution using Gaussian Elimination. I belive LU decomposition will work better on this kind of matrix though.
An easier particular case is when M = N.
This is the easier case? I can't even tell if this is an integer...
Let F be a field with an element ω of order n i.e. ωn = 1. Then
is like 
. From 
, we can get 
for any integer k using Chebyshev polynomials. If the base field has no such ω, we can extend this field to
F[X] / (Xn - 1). Edit: X^n-1 probably doesn't work. Just generate some irreducible polynomial.I think, using that, we can solve the problem (taking word-size prime mod) in
time. There is a similar formula for n ≠ m case which can be used to get similar time bound. I haven't implement any of these so I'm not sure if this really works.
You can use the Kirchhoff Theorem! It has the same complexity as computing the determinant of a matrix (which is polynomial, using Gaussian Elimination).
This Spoj problem is exactly what you describe :) Maze