Skip to content

Instantly share code, notes, and snippets.

@nmakeenkov nmakeenkov/main.kt

Created Sep 26, 2019
Embed
What would you like to do?
Avoid Prefix Palindromes
const val INF : Long = 1000 * 1000 * 1000 + 9
// n^k
fun pow(n: Long, k: Int): Long =
when
{
k == 0 -> 1L
(k % 2) == 0 ->
{
val x = pow(n, k / 2)
(x * x) % INF
}
else -> (pow(n, k - 1) * n) % INF
}
fun main(args: Array<String>)
{
val input = readLine()!!.split(" ").map { Integer.parseInt(it) }.toList()
val n = input[0]
val k = input[1].toLong()
val dp = LongArray(n + 1)
dp[1] = k
var sumK = 0L
for (v in 2..n)
{
if (v % 2 == 1)
{
sumK = (sumK * k + dp[v / 2 + 1]) % INF
}
dp[v] = (INF + pow(k, (v + 1) / 2) - sumK) % INF
}
println(dp[n])
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.