9592. Конкатенация двух палиндромов

Найдите количество способов, которыми можно построить строку длины n используя k латинских букв (размер алфавита равен k) в виде конкатенации двух непустых палиндромов.

Вход. Два натуральных числа n и k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 26).

Выход. Выведите количество способов построить заданную строку. Ответ вывести по модулю 10⁹ + 7.

Пример входа 1	Пример выхода 1
4 1	3
Пример входа 2	Пример выхода 2
3 2	8

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Представим строку длины n в виде конкатенации двух непустых палиндромов длин l и n – l.

Рассмотрим палиндром длины l. Поскольку палиндром читается одинаково слева направо и справа налево, его вторая половина полностью определяется первой. Поэтому достаточно произвольно выбрать только первые (l + 1) / 2 символов: каждый из них может быть любой из k букв алфавита. Оставшиеся символы однозначно восстанавливаются так, чтобы строка была палиндромом.

Таким образом, общее количество палиндромов длины l равно k^(l+1)/2.

Аналогично, для палиндрома длины n – l его вторая половина полностью определяется первой. Поэтому первые (n – l + 1) / 2 символов можно выбрать произвольным образом, выбирая каждый из них из k букв алфавита, а остальные символы однозначно определяются условием палиндрома.

Следовательно, количество палиндромов длины n – l равно k^(n-l+1)/2.

Построить конкатенацию двух палиндромов с длинами l и n – l можно

k^(l+1)/2 * k^(n-l+1)/2

способами. Поскольку ни один из палиндромов не должен быть пустым, то 1 ≤ l ≤ n – 1. Общее количество возможных палиндромов равно

Все операции следует проводить по модулю 10⁹ + 7.

Пример

Рассмотрим второй пример, в котором длина строки равна 3, а алфавит состоит из двух букв. Пусть это будут буквы a и b.

· Палиндромы длины 1: a и b.

· Палиндромы длины 2: aa и bb.

Таким образом, существует ровно 8 искомых строк длины 3:

Реализация алгоритма

Вычисления проводятся по модулю 10⁹ + 7. Определим модуль MOD.

#define MOD 1000000007

Функция powmod вычисляет значение xⁿ mod m.

long long powmod(long long x, long long n, long long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);

return (x * powmod(x, n - 1, m)) % m;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &n, &k);

Вычисляем ответ res по формуле.

res = 0;

for (l = 1; l < n; l++)

res = (res + powmod(k, (l + 1) / 2, MOD) *

powmod(k, (n - l + 1) / 2, MOD)) % MOD;

Выводим ответ.

printf("%lld\n", res);

Java реализация

import java.util.*;

public class Main

{

public final static long MOD = 1000000007;

static long PowMod(long x, long n, long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

return (x * PowMod(x, n - 1, m)) % m;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n = con.nextLong();

long k = con.nextLong();

long res = 0;

for (long l = 1; l < n; l++)

res = (res + PowMod(k, (l + 1) / 2, MOD) *

PowMod(k, (n - l + 1) / 2, MOD)) % MOD;

System.out.println(res);

con.close();

}

}

Python реализация

Вычисления проводятся по модулю 10⁹ + 7. Определим модуль mod.

mod = 10 ** 9 + 7

Читаем входные данные.

n, k = map(int, input().split())

Вычисляем ответ res по формуле.

res = 0;

for l in range(1,n):

res = (res + pow(k, (l + 1) // 2, mod) *

pow(k, (n - l + 1) // 2, mod)) % mod;

Выводим ответ.

print(res)