İki palindromun konkatenasiyası#9592

İki palindromun konkatenasiyası (Həll təhlili)

Strinqi uzunluğu $n$ olan iki boş olmayan palindrome uzunluqları $l$ və $n - l$ n - l olaraq təmsil edək.

Uzunluğu $l$ olan palindrome nəzərdən keçirək. Çünki palindrome həm sağdan sola, həm də soldan sağa eyni şəkildə oxunur, onun ikinci yarısı tamamilə birinci yarı ilə müəyyən edilir. Buna görə yalnız ilk $(l + 1) /2$ (l + 1) / 2 simvollarını sərbəst seçmək kifayətdir: onların hər biri $k$ hərfi olan əlifbadan hər hansı biri ola bilər. Qalan simvollar palindrome olmaq şərti ilə dəqiq olaraq bərpa edilir.

Beləliklə, uzunluğu $l$ olan palindrome-ların ümumi sayı $k^{(l + 1) /2}$ k^{(l+1)/2}-ə bərabərdir.

Bənzər şəkildə, uzunluğu $n - l$ n - l olan palindrome üçün ikinci yarısı tamamilə birinci yarı ilə müəyyən edilir. Buna görə ilk $(n - l + 1) /2$ (n - l + 1) / 2 simvolları sərbəst şəkildə seçilə bilər, kitab $k$ hərfi olan əlifbadan hər hansı biri ola bilər və qalan simvollar palindrome olmaq şərti ilə dəqiq müəyyən edilir.

Nəticədə, uzunluğu $n - l$ n - l olan palindrome-ların sayı $k^{(n - l + 1) /2}$ k^{(n-l+1)/2}-ə bərabərdir.

Uzunluqları $l$ və $n - l$ n - l olan iki palindrome-u birləşdirmək

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

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

şəkillərdə mümkündür. Çünki heç bir palindrome boş olmamalıdır, onda $1 \leq l \leq n - 1$ 1 \le l \le n - 1. Mümkün palindrome-ların ümumi sayı belədir

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}

Bütün əməliyyatlar $1 0^{9} + 7$ 10^9 + 7 moduluna görə həyata keçirilməlidir.

Misal

Simvollardan ibarət olan ikinci misalı nəzərdən keçirək, burada hərflərdən ibarət seriya $3$ uzunluğundadır və əlifba iki hərfdən ibarətdir. Bunlar $a$ və $b$ hərfləri olsun.

Uzunluğu $1$ olan palindrome-lar: $a$ və $b$ .
Uzunluğu $2$ olan palindrome-lar: $aa$ və $bb$ .

Beləliklə, tam olaraq $8$ axtarılan simvol uzunluğu $3$ var:

Alqoritmin reallaşdırılması

Hesablama $1 0^{9} + 7$ 10^9 + 7 moduluna görə aparılır. Modulu $M O D$ olaraq təyin edək.

#define MOD 1000000007

powmod funksiyası $x^{n} m o d m$ x^n~mod~m dəyərini hesablayır.

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

Əsas proqramın hissəsi. Giriş məlumatlarını oxuyuruq.

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

Formulaya görə cavabı $r es$ hesablayırıq.

res = 0;
for (l = 1; l < n; l++)
  res = (res + powmod(k, (l + 1) / 2, MOD) * 
               powmod(k, (n - l + 1) / 2, MOD)) % MOD;

Cavabı çıxardırıq.

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

Java reallaşdırması

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 reallaşdırması

Hesablama $1 0^{9} + 7$ 10^9 + 7 moduluna görə aparılır. Modulu $m o d$ olaraq təyin edək.

mod = 10 ** 9 + 7

Giriş məlumatlarını oxuyuruq.

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

Formulaya görə cavabı $r es$ hesablayırıq.

res = 0;
for l in range(1,n):
  res = (res + pow(k, (l + 1) // 2, mod) * 
               pow(k, (n - l + 1) // 2, mod)) % mod;

Cavabı çıxardırıq.

print(res)