Can anyone please provide any hint for this problem? Throwing Dice
→ Pay attention
Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
26:02:29
Register now »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
26:02:29
Register now »
*has extra registration
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/22/2024 15:32:31 (k2).
Desktop version, switch to mobile version.
Supported by
Let f(n) be the number of ways of throwing dices to get a sum of n, Then consider the last dice throw. It has 6 possibilities 1-6. So f(n) = f(n-1) + f(n-2) + ... + f(n-6).
The recurrence is correct. However, unfortunately, it TLE's. There is hope though. This is a linear recurrence can be computed for arbitrary values of n using fast matrix exponentiation. Here is a geeks for geeks article that illustrates the technique in action https://www.geeksforgeeks.org/find-nth-term-a-matrix-exponentiation-example/
My fav trick in such problems:
1. precalc first 20 values
2. use Berlekamp-Massey algorihm to compute n_th value of Linear recurrence
source: https://mirror.codeforces.com/blog/entry/61306?
another problems:
https://mirror.codeforces.com/contest/392/submission/51596991
https://mirror.codeforces.com/contest/678/submission/51597127