9616. Anti-palindromic strings

 

Given two integers n and m, compute the number of strings of length n over an alphabet of size m that do not contain any substring which is a palindrome of length greater than one.

 

Input. The first line contains the number of test cases t. Each test case consists of a single line containing two integers n and m (1 ≤ n, m ≤ 109).

 

Output. For each test case, print the required number of strings modulo 109 + 7.

 

Sample input

Sample output

2

5 6

6 5

1920

1620

 

 

SOLUTION

exponentiation

 

Algorithm analysis

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

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

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

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

 

Algorithm implementation

Define the modulus under which all computations will be performed.

 

#define MOD 1000000007

 

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

}

 

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

}