In the problem Stamp Painting I found an O(log(n)), 1-liner formula that passes 10/12 cases (it fails on test cases 2 and 11).
cout << (((n-k+1)*binpow(m,n-k+1)-(n-k)*binpow(m,n-k))%MOD+MOD)%MOD << "\n";
(binpow is binary exponentiation, and MOD = 1e9+7)
After some stresstesting, I’ve found that this formula works on roughly 75% of cases for random N, M, and K.
Because I guessed the formula, I’m not quite sure why it works (and why sometimes it doesn’t work). Can someone enlighten me?
Thanks in advance!