Gagandeep98's blog

CSES : Mathematics Throwing Dice
By Gagandeep98, history, 4 years ago, In English

Can anyone please provide any hint for this problem? Throwing Dice

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

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://codeforces.me/blog/entry/61306?
another problems:
https://codeforces.me/contest/392/submission/51596991
https://codeforces.me/contest/678/submission/51597127

→ Reply