Antipalindromik sətrlər (Həll təhlili)

Əgər bir sıra uzunluğu $2$ və ya $3$ olan palindrome alt stringlər içərmirsə, onda o, ümumiyyətlə birdən uzun palindrome alt stringlər içərmir.

Əgər n = 1 olarsa, uzunluğu $1$ olan bir sıra $m$ hərfdən istənilən birini təşkil edə bilər. Bu halda uyğun olan sıranın sayı $m$ olur.

Əgər m = 1 və n > 1 olarsa, cavab $0$ bərabərdir, çünki $aa..aa$ formasında yalnız bir mümkün sıra mövcuddur və o, palindrome $aa$-nı içərir.

Əgər n = 2 olarsa, sıranın birinci pozisiyasında istənilən $m$ hərfi yerləşə bilər və ikinci pozisiyada — qalan m - 1 hərfdən istənilən biri. Birinci və ikinci pozisiyalardakı hərflər eyni olmamalıdır, əks halda onlar uzunluğu $2$ olan palindrome yaradırlar. Beləliklə, aranan sıranın sayı bərabərdir

Güman edək ki, sıranın uzunluğu $2$-dən böyükdür. Birinci pozisiyada istənilən $m$ hərfi, ikinci pozisiyada istənilən m - 1 hərfi ola bilər. Üçüncü pozisiyadakı hərf palindrome uzunluğu $2$ olmasın deyə ikinci pozisiyadakı hərfdən fərqlənməlidir, həmçinin birinci pozisiyadakı hərfdən fərqlənməlidir ki, ilk üç simvol uzunluğu $3$ olan palindrome yaratmasın. Beləliklə, üçüncü pozisiyada istənilən m - 2 hərfi ola bilər.

Bu məntiqi izləərək anlayırıq ki, $i$-ci pozisiyadakı hərf i - 1 və i - 2 pozisiyalarındakı hərflərdən fərqlənməlidir. Beləliklə, üçüncü pozisiyadan başlayaraq hər bir pozisiya üçün hərfin seçilməsi üçün tam olaraq m - 2 icazə verilmiş seçim variantı var.

Beləliklə, aranan sıranın sayı bərabərdir

Alqoritmin tətbiqi

Bütün hesablamaların yerinə yetirildiyi modulu elan edirik.

#define MOD 1000000007

powmod funksiyası 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;
}

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

scanf("%d", &tests);
while (tests--)
{
  scanf("%lld %lld", &n, &m);

$n$ və $m$ dəyərlərinə əsasən cavabı hesablayırıq.

  if (n == 1) res = m; else
  if (m == 1) res = 0; else // n > 1, m = 1:  aa....a
  if (n == 2) res = (m * (m - 1)) % MOD; else
  res = ((m * (m - 1)) % MOD * powmod(m - 2, n - 2, MOD)) % MOD;

Cavabı çıxarırıq.

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