Gagandeep98's blog

By Gagandeep98, history, 5 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

| Write comment?
»
5 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).

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