Smaller Strings Solution Google Kickstart 2021

Table of Contents

Problem

You are given an integer KK and a string SS of length NN, consisting of lowercase letters from the first KK letters of the English alphabet. Find the number of palindrome strings of length NN which are lexicographically smaller than SS and consist of lowercase letters from the first KK letters of the English alphabet.

A string composed of ordered letters a1,a2,…,ana1,a2,…,an is lexicographically smaller than another string of the same length b1,b2,…,bnb1,b2,…,bn if ai<biai<bi, where ii is the first index where characters differ in the two strings. For example, the following strings are arranged in lexicographically increasing order: aaa, aab, aba, cab.

A palindrome is a string that is the same written forwards and backwards. For example, anna, racecar, aaa and x are all palindromes, while ab, frog and yoyo are not.

As the number of such strings can be very large, print the answer modulo 109+7109+7.

Input

The first line of the input gives the number of test cases, TT. TT test cases follow.

Each test case consists of two lines. The first line contains two integers NN and KK. The second line contains a string SS of length NN, consisting of lowercase letters.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the number of lexicographically smaller palindrome strings modulo 109+7109+7.

Limits

Memory limit: 1 GB.
1≤T≤1001≤T≤100.
The string SS consists of lowercase letters from the first KK letters of the English alphabet.

Test Set 1

Time limit: 20 seconds.
1≤N≤81≤N≤8.
1≤K≤51≤K≤5.

Test Set 2

Time limit: 10 seconds.
1≤N≤1051≤N≤105.
1≤K≤261≤K≤26.

Sample

Sample Input

3
2 3
bc
5 5
abcdd
1 5
d

Sample Output

Case #1: 2
Case #2: 8
Case #3: 3

In Sample Case #1, the palindromes are ["aa", "bb"].

In Sample Case #2, the palindromes are ["aaaaa", "aabaa", "aacaa", "aadaa", "aaeaa", "ababa", "abbba", "abcba"].

In Sample Case #3, the palindromes are ["a", "b", "c"].

Also Read:

Solution:

#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll mod = 1'000'000'007;

ll modpow(ll x, ll e) {
	if (e == 0) return 1;
	ll a = modpow(x, e >> 1);
	a = a * a % mod;
	if (e & 1) a = a * x % mod;
	return a;
}

void solve() {
	int N, K;
	cin >> N >> K;
	string str;
	cin >> str;
	ll res = 0;
	rep(i,0,(N+1)/2) {
		// mismatch at i, then any
		int d = str[i] - 'a';
		res += d * modpow(K, (N+1)/2 - i - 1) % mod;
	}
	rep(i,(N+1)/2,N) {
		int j = N-1 - i;
		if (str[j] == str[i]) continue;
		if (str[j] < str[i]) {
			res++;
		}
		break;
	}
	cout << res % mod << endl;
}

int main() {
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit | cin.eofbit | cin.badbit);
	cin.tie(0);
	int T;
	cin >> T;
	rep(i,0,T) {
		cout << "Case #" << i+1 << ": ";
		solve();
	}
}

Smaller Strings Solution Google Kickstart 2021