Конкатенація двох паліндромів#9592

Конкатенація двох паліндромів (Розбір)

Уявімо рядок довжини $n$ у вигляді конкатенації двох непустих паліндромів довжин $l$ та $n - l$ n - l.

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

Таким чином, загальна кількість паліндромів довжини $l$ дорівнює $k^{(l + 1) /2}$ k^{(l+1)/2}.

Аналогічно, для паліндрома довжини $n - l$ n - l його друга половина повністю визначається першою. Тому перші $(n - l + 1) /2$ (n - l + 1) / 2 символів можна обрати довільним чином, обираючи кожен з них з $k$ букв алфавіту, а інші символи однозначно визначаються умовою паліндрому.

Відповідно, кількість паліндромів довжини $n - l$ n - l дорівнює $k^{(n - l + 1) /2}$ k^{(n-l+1)/2}.

Побудувати конкатенацію двох паліндромів з довжинами $l$ та $n - l$ n - l можна

k^{(l + 1) /2} \cdot k^{(n - l + 1) /2}

k^{(l+1)/2} \cdot k^{(n-l+1)/2}

способами. Оскільки жоден з паліндромів не повинен бути пустим, то $1 \leq l \leq n - 1$ 1 \le l \le n - 1. Загальна кількість можливих паліндромів дорівнює

l = 1 \sum n - 1 k^{\frac{( l + 1 )}{2}} \cdot k^{\frac{( n - l + 1 )}{2}}

\sum_{l=1}^{n-1} k^{(l+1) \over 2} \cdot k^{(n-l+1) \over 2}

Всі операції слід проводити за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклад

Розглянемо другий приклад, у якому довжина рядка дорівнює $3$ , а алфавіт складається з двох букв. Нехай це будуть букви $a$ та $b$ .

Паліндроми довжини $1$ : $a$ та $b$ .
Паліндроми довжини $2$ : $aa$ та $bb$ .

Таким чином, існує рівно $8$ шуканих рядків довжини $3$ :

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

Виконання розрахунків проводиться за модулем $1 0^{9} + 7$ 10^9 + 7. Визначимо модуль $M O D$ .

#define MOD 1000000007

Функція powmod обчислює значення $x^{n} m o d m$ x^n~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);

Обчислюємо відповідь $r es$ за формулою.

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();
  }
}

Java

Python реалізація

Розрахунки проводяться за модулем $1 0^{9} + 7$ 10^9 + 7. Визначимо модуль $m o d$ .

mod = 10 ** 9 + 7

Читаємо вхідні дані.

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

Обчислюємо відповідь $r es$ за формулою.

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)