Anti-palindromic strings (Editorial)

If a string does not contain palindromic substrings of length $2$ or $3$, then it does not contain palindromic substrings of length greater than one at all.

If n = 1, then a string of length $1$ can consist of any of the $m$ letters. In this case, the number of valid strings is $m$.

If m = 1 and n > 1, then the answer is $0$, since there is only one possible string of the form $aa..aa$, and it contains the palindrome $aa$.

If n = 2, then the first position of the string can contain any of the $m$ letters, and the second position can contain any of the remaining m - 1 letters. The letters in the first and second positions must be different; otherwise, they would form a palindrome of length $2$. Therefore, the number of valid strings is

Let the length of the string be greater than $2$. The first position can contain any of the $m$ letters, and the second position can contain any of the remaining m - 1 letters. The letter in the third position must be different from the letter in the second position to avoid forming a palindrome of length $2$, and also different from the letter in the first position so that the first three characters do not form a palindrome of length $3$. Therefore, the third position can contain any of the m - 2 letters.

Following this logic, we conclude that the letter at the $i$-th position must be different from the letters at positions i - 1 and i - 2. Thus, for each position starting from the third, there are exactly m - 2 valid choices for the letter.

Therefore, the number of valid strings is

Algorithm implementation

Define the modulus under which all computations will be performed.

#define MOD 1000000007

The function powmod computes the value of 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;
}

The main part of the program. Read the input data.

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

Compute the answer depending on the values of $n$ and $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;

Print the answer.

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