9616. Анти палиндромные строки

 

Даны два числа n и m. Посчитайте количество строк длины n, составленных из символов алфавита мощности m, которые не содержат ни одной подстроки, являющейся палиндромом длины больше единицы.

 

Вход. В первой строке задано количество тестов t. Каждый тест состоит из одной строки, содержащей два целых числа n и m (1 ≤ n, m ≤ 109).

 

Выход. Для каждого теста выведите искомое количество строк по модулю 109 + 7.

 

Пример входа

Пример выхода

4

3 6

1 3

3 1

2 4

120

3

0

12

 

 

РЕШЕНИЕ

возведение в степень

 

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

Если строка не содержит подстрок-палиндромов длины 2 или 3, то она не содержит подстрок-палиндромов длины больше единицы вообще.

Если n = 1, то строка длины 1 может состоять из любой из m букв. В этом случае количество подходящих строк равно m.

Если m = 1 и n > 1, то ответ равен 0, так как существует единственная возможная строка вида aa..aa, и она содержит палиндром aa.

Если n = 2, то на первой позиции строки может стоять любая из m букв, а на второй позиции – любая из m – 1 оставшихся букв. Буквы на первой и второй позициях не должны совпадать, иначе они образуют палиндром длины 2. Следовательно, количество искомых строк равно

(m * (m – 1)) mod 109 + 7

Пусть длина строки больше 2. На первой позиции может находиться любая из m букв, на второй – любая из m – 1 букв. Буква на третьей позиции должна отличаться от буквы на второй позиции, чтобы не образовывался палиндром длины 2, а также отличаться от буквы на первой позиции, чтобы первые три символа не образовывали палиндром длины 3. Следовательно, на третьей позиции может находиться любая из m – 2 букв.

Следуя этой логике, приходим к выводу, что буква на i-ой позиции должна отличаться от букв на позициях i – 1 и i – 2. Таким образом, для каждой позиции, начиная с третьей, имеется ровно m – 2 допустимых вариантов выбора буквы.

Следовательно, количество искомых строк равно

(m * (m – 1) * (m – 2)n – 2) mod 109 + 7

 

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

Объявим модуль, по которому будут выполняться все вычисления.

 

#define MOD 1000000007

 

Функция powmod вычисляет значение xn 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);

}