We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
There is a way to beat all test cases. Initially I used pure combinatorics but this proved to be too slow. One can notice that frequencies of given scores are the coefficients of followinng polynomial P(x) = x + x^2 + ... x^d raised to power n P(x)^n where n is the number of dice. Calculating it directly is way to inefficient, but we can use FFT, specifically its special variant NTT(Number Theoretic Transform). As a n-th root of unity we can use g^k where g in our case is primitive root modulo 1012924417 and k = 483. So we can use direct FFT to get Y vector, then raise every element of the vector to the proper power and then use inverse FFT to get the vector P(x)^n.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #205: Dice Game
You are viewing a single comment's thread. Return to all comments →
There is a way to beat all test cases. Initially I used pure combinatorics but this proved to be too slow. One can notice that frequencies of given scores are the coefficients of followinng polynomial P(x) = x + x^2 + ... x^d raised to power n P(x)^n where n is the number of dice. Calculating it directly is way to inefficient, but we can use FFT, specifically its special variant NTT(Number Theoretic Transform). As a n-th root of unity we can use g^k where g in our case is primitive root modulo 1012924417 and k = 483. So we can use direct FFT to get Y vector, then raise every element of the vector to the proper power and then use inverse FFT to get the vector P(x)^n.