Question
The convolution $a*b=\left(c_{0},c_{1},\ldots,c_{n+m-2}\right)$ of two vectors $\left(a_{0},\ldots,a_{n-1}\right)$ and $\left(b_{0},\ldots,b_{m-1}\right)$ is defined as follows: $$ \left(a*b\right)_{i}=c_{i}=\sum_{j=0}^{i}a_{j}b_{i-j} $$
Given that by using the $FFT$ algorithm the convolution can be calculated in $O\left(n\log n\right)$, suggest an algorithm that calculates the number of ways to generate each number in $\left\{ n,\ldots,6n\right\} $ by throwing $n$ dice in $O\left(n\log n\right)$.
My Take
I tought on defining the following vectors: $$ V_{A}\left[i\right]=V_{B}\left[i\right]=\begin{cases} 1 & \text{i is a possible result for n dice throws}\\ 0 & \text{else} \end{cases} $$ For example, if n = 2 then: $$ V_{A}=V_{B}=\left[\underbrace{0}_{1},\underbrace{1}_{2},\underbrace{1}_{3},\underbrace{1}_{4},\underbrace{1}_{5},\underbrace{1}_{6},\underbrace{1}_{7},\underbrace{1}_{8},\underbrace{1}_{9},\underbrace{1}_{10},\underbrace{1}_{11},\underbrace{1}_{12}\right] $$ So the convolution would be: $$ c_{i}=\sum_{j=0}^{i}V_{A}\left[j\right]V_{B}\left[i-j\right] $$ when $c_{i}$ contains the possible ways to get $i$ as the sum of $n$ throws.
For example: $$ c_{2}=\underbrace{V_{A}\left[0\right]V_{B}\left[2\right]}_{0}+\underbrace{V_{A}\left[1\right]V_{B}\left[1\right]}_{1}+\underbrace{V_{A}\left[1\right]V_{B}\left[0\right]}_{0}=1 $$ So there is only one way to get 2 as the sum of two dice throws.
Well, I think it works for $n=2$ but it gets complicated for $n>2$, and I don't think it works in $O\left(n\log n\right)$ anymore.
When $n=3$ I will define: $$ V_{A}=V_{B}=\left[\underbrace{0}_{1},\underbrace{0}_{2},\underbrace{1}_{3},\underbrace{1}_{4},\underbrace{1}_{5},\underbrace{1}_{6},\underbrace{1}_{7},\ldots,\underbrace{1}_{23},\underbrace{1}_{24}\right] $$
So for example: $$ c_{8}=\underbrace{V_{A}\left[0\right]V_{B}\left[8\right]}_{0}+\ldots+\underbrace{V_{A}\left[3\right]V_{B}\left[5\right]}_{1}+\underbrace{V_{A}\left[4\right]V_{B}\left[4\right]}_{1}+\underbrace{V_{A}\left[5\right]V_{B}\left[3\right]}_{1}+\ldots+\underbrace{V_{A}\left[8\right]V_{B}\left[0\right]}_{0}=3 $$
That is incorrect, because in this case I need to find the number of possible ways to get 3,4 and 5.
This is where I got stuck. I don't know if my idea is good and if it's possible to use it and stay at $O\left(n\log n\right)$. I think it gets recursive and complicated.