Number of ways in which one can start from any node and return to it in K steps (complete graph) Given two integers N & K, consider a complete graph(every pair of distinct vertices is connected by a unique edge.) of N nodes. Calculate the number of ways in which one can start from any node and return to it in K steps. Output answer % 1000000007.
Here's the link to the question.
https://www.hackerearth.com/problem/algorithm/pablo-safe-houses/
How to solve this question?Also in the editorial section it is mentioned that it can be solved using Matrix Exponentiation, what would be the recurrence relation?
 A: There was some talk about a recurrence relation and matrix exponentiation. 
Let $n_{i, t}$ be the number of ways to get to node $i$ in $t$ steps. The recurrence is $n_{i,t} = n_{1, t-1} + n_{2, t-1} + ... + n_{N, t-1}$ where only $n_{i,t-1}$ does not appear on the left hand side since it is impossible to travel from $i$ to $i$ in one step.
Notating $n_{1, t} ... n_{N, t}$ as the $N$ dimensional vector $n_t$, the recurrence can be turned into a linear operator $n_t = (P - I)n_{t-1}$ where $P$ is the matrix of all ones and $P-I$ is the matrix of all ones except zeros on the diagonal.
The answer then is any term on the diagonal of $(P-I)^k$.
A: Call the answer $f(n, k)$.
If you start and end from node $1$, you have $(k-1)$ choices to make for the intermediate nodes since you lose a choice for the last day. For each intermediate choice, you have $n-1$ options. This would yield $(n-1)^{k-1}$ but then we have to remove all the choices that have the second to last entry as $1$. But we know these exactly as $f(n, k-1)$.
Your recurrence is $f(n,k) = (n-1)^{k-1} - f(n,k-1)$.
The base case is $f(n, 2) = n-1$.
Expanding out a couple of times you will begin to see a pattern. $f(n,k) = (n-1)^{k-1} - (n-1)^{k-2} + (n-1)^{k-3} ... (n-1)$
This expression looks something like this

int total = 0;
int power_of_neg_n_minus_1 = 1;
for (int i = 0; i < k-1; ++i) {
    power_of_n_minus_1 *= -(n-1);
    total += power_of_neg_n_minus_1;
}
// just in case we got - + - + ... instead of + - + - ....
if (total < 0) { total *= -1 };

The only problem here is that you will overflow the int so you need to take % inside the loop. Also you might need to be aware of the behavior of % on negative ints.
