Anti-Palindromic Strings : Challenge | 101 Hack November'14 | HackerRank

Anti-Palindromic Strings : Challenge | 101 Hack November'14 | HackerRank
You are given two integers, $N$ and $M$. Count the number of strings of length $N$ under the alphabet set of size $M$ that doesn't contain any palindromic string of the length greater than $1$ as a consecutive substring.

For the 2nd test case, we have an alphabet of size M = 3. For the sake of simplicity, let's consider the alphabet as [A, B, C]. We can construct nine strings of size N = 2 using these letters.

AA
AB
AC
BA
BB
BC
CA
CB
CC

Save AA, BB, and CC, all the strings satisfy the given condition; hence, the answer 6.

First we have to realize that the anti-palindromic string is a string that does not contain any palindromic substrings of the length of  and , because all the palindromic strings of the greater lengths contain at least one palindromic substring of the length of  or  - basically in the center.

So, the following is true:

• There are  ways to choose the first symbol of the string;
• Then there are  ways to choose the second symbol of the string - basically it should not be equal to the first one;
• Then there are  ways to choose any next symbol - basically it should not coincide with the previous symbols, that aren't equal.

Knowing this, we can write the answer in the following ways:

• If , then the answer is ;
• If , then the answer is ;
• If , then the answer is .

For finding  you can use binary exponentiation.

https://github.com/PoeLoren/hackerrank/blob/master/AntiPalindromic%20Strings.cpp
long long  square(long long a, long long b)
{
        if(b <= 0)
            return 1;
        if(b == 1)
            return a;
        if(b % 2 == 1){
            long long tmp = square(a, b / 2);
            return tmp * tmp % MOD * a % MOD;
        }else{
            long long tmp = square(a, b / 2);
            return tmp * tmp % MOD;
        }
}

int main() {
    int t;
    cin >> t;
    while(t--){
        long long m, n;
        cin >> n >> m;
        if(m == 1 && n == 1){
            cout << "1" << endl;
            continue;
        }
        if(m == 1){
            cout << "0" << endl;
            continue;
        }
        if(n == 1){
            cout << m << endl;
            continue;
        }
        long long res = 0;
        res = m * (m - 1) % MOD;
        if(n >= 3)
            res = res * square(m-2, n - 2);
        cout << res % MOD<< endl;
    }
    return 0;
}
http://lealgorithm.blogspot.com/2015/03/hackerrank-antipalindromic-strings.html

Read full article from Anti-Palindromic Strings : Challenge | 101 Hack November'14 | HackerRank