Анти-паліндромні рядки (Розбір)

Якщо рядок не містить підрядків-паліндромів довжини $2$ або $3$, то він не містить підрядків-паліндромів довжини більше одиниці взагалі.

Якщо n = 1, то рядок довжини $1$ може складатися з будь-якої з $m$ букв. В цьому випадку кількість підходящих рядків дорівнює $m$.

Якщо m = 1 і n > 1, то відповідь дорівнює $0$, так як існує єдиний можливий рядок виду $aa..aa$, і він містить паліндром $aa$.

Якщо n = 2, то на першій позиції рядка може стояти будь-яка з $m$ букв, а на другій позиції — будь-яка з m - 1 останніх букв. Букви на першій і другій позиції не повинні збігатися, інакше вони утворюють паліндром довжини $2$. Отже, кількість шуканих рядків дорівнює

Нехай довжина рядка більше $2$. На першій позиції може знаходитися будь-яка з $m$ букв, на другій — будь-яка з m - 1 букв. Буква на третій позиції повинна відрізнятися від букви на другій позиції, щоб не утворювався паліндром довжини $2$, а також відрізнятися від букви на першій позиції, щоб перші три символи не утворювали паліндром довжини $3$. Отже, на третій позиції може знаходитися будь-яка з m - 2 букв.

Слідуючи цій логіці, приходимо до висновку, що буква на $i$-ій позиції повинна відрізнятися від букв на позиціях i - 1 і i - 2. Таким чином, для кожної позиції, починаючи з третьої, є рівно m - 2 допустимих варіантів вибору букви.

Отже, кількість шуканих рядків дорівнює

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

Оголосимо модуль, за яким будуть виконуватися всі обчислення.

#define MOD 1000000007

Функція powmod обчислює значення 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", &tests);
while (tests--)
{
  scanf("%lld %lld", &n, &m);

Вираховуємо відповідь в залежності від значень $n$ і $m$.

  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;

Виводимо відповідь.

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