Could someone explain in detail how to solve this problem. The editorialist talks about matrix exponentiation. I know how to apply this when we solve linear equation, like F(N) for fibonacci series. But here we want to apply it on dp[i][j] where dp[i][j] = number of lists whose sum is i and last number is j. How we solve it.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 08:19:48 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by thedark (previous revision, new revision, compare).
Let DP(S, x) denote the number of lists with sum S and last element x.
Note that DP(S, x) depends on DP(S-x, y), where abs(x-y) <= d.
For calculating DP(S, x), Keep a m*m matrix consisting of combinations of DP(S2, y), where S-m <= S2 <= S-1 and 1 <= y <= m. Fill the entries of the transition matrix based on allowed transitions (i.e. abs(x-y) <= d).
Time complexity is O(m^6 * log(S)).
Could you elaborate, I mean in steps how is it being carried out.
Create an initial vector of length m*m containing the result for the first m values of s. Eg. for m = 3 it would be
F0 = [dp[0][0], dp[0][1], dp[0][2], dp[1][0], dp[1][1], dp[1][2], dp[2][0], dp[2][1], dp[2][2] ]
Now we need to build a m*m by m*m matrix that transitions to the vector
F1 = [dp[1][0], dp[1][1], dp[1][2], dp[2][0], dp[2][1], dp[2][2], dp[3][0], dp[3][1], dp[3][2]]
The first (m-1)*m rows will have just a single 1 to effectively "shift" the last (m-1)*m entries of F0 to the first (m-1)*m entries of F1. The last m rows of the transition matrix will have some ones to implement the dp formula (note that it will depend on the value of d).
Could you please elaborate on the generator matrix for exponentiation
I didn't know it was solvable by matrix exponentiation, I just coded a divide and conquer approach. My idea was setting the limits on the leftmost and rightmost number (for example if before the leftmost number there was a 4 and d = 2 then the limits were from 2 to 6) and choose the middle number, and then divide and conquer. When s <= 30 just tried all possible numbers for the leftmost until s = 0. All of this with memoization.