There are $k$ warriors that participate in the Wars, which have happened for the past $n$ years. Each year there has been a victor. Further, a particular warrior $W$ has won the Wars an even number of times. Also, $W$ didn't participate in the first year.
One day, you wonder in how many possible ways the victories in the previous years could have taken place (that is, the number of different sequences of victors possible). Output the result of this complicated (and senseless) calculation.
I need help to find the number of ways in which victories during $n$ years could have taken place,modulo $1000000007$ $(10^9 + 7)$.
ex: $n=1,k=4$
$\text{ans}=3$
$n=3, k=3$
$\text{ans}=10$
I have arrived to this formula
sum of pow(n-1,i-1)*C(n-1,i-1)
where $C(n-1,i-1)$ is $\binom{n-1}{i-1}$.
Can someone help me to further simplify this formula or can provide me another formula which does not involve factorials as the value of $n$ and $k$ can vary from
$1 \leq n,k \leq 10^9$?
If you consider the binomial series expansions of $((k-1)+1)^n$ and $((k-1)-1)^n$ and add them up, it is clear that the answer you are looking for is $(k^n + (k-2)^n)/2$.
If you use the repeated squaring method to find the nth powers, I believe you can find this really fast.
EDIT: 'W didn't participate in the first year' Didn't account for this earlier. Updating.
With this condition, we just solve for the last (n-1) matches like earlier, then multiply by (k-1).
So now we get $(k-1) \times (k^{n-1} + (k-2)^{n-1})/2$. Again, easy to compute.
EDIT 2: As requested, showing more details:
Number of ways we can have (n-1) games with W winning even number of them = $\sum_{i=0}^{i=(n-1)/2}{{n-1}\choose{2i}}(k-1)^{n-1-2i}$ = $\sum_{i=0}^{i=(n-1)/2}{{n-1}\choose{2i}}(k-1)^{2i}$ (just replace 2i by n - 1 - 2i and use the fact that ${n \choose k} = {n \choose {n-k}}$). Call this $C_1$.
Similarly, define $\sum_{i=0}^{i=(n-1)/2}{{n-1}\choose{2i+1}}(k-1)^{2i+1}$ as $C_2$ (I have not been very careful with the max value of i when (n-1) is odd versus even etc. but this is simpler to deal with: just take ${n \choose k} = 0$ when k>n).
$C_1 + C_2 = ((k-1)+1)^{n-1} = k^{n-1}$ (by binomial theorem). Similarly, $C_1 - C_2 = ((k-1)-1)^{n-1} = (k-2)^{n-1}$, again by binomial theorem.
Adding these two equations, $2C_1 = k^{n-1} + (k-2)^{n-1}$.
So $C_1 = \frac{k^{n-1} + (k-2)^{n-1}}{2}$.
Now, for every way in which the last n - 1 games can be decided, the first game can be decided in (k-1) ways (any of the k-1 players other than W can win). So the total answer we want = $(k-1) \times C_1$ = $(k-1) \times \frac{k^{n-1} + (k-2)^{n-1}}{2}$