(1) Smaller Strings

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

A string composed of ordered letters a1,a2,…,an is lexicographically smaller than another string of the same length b1,b2,…,bn if ai<bi, where i 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 .

问题简述

给定字符串长度为N，仅包含字母表上的前K个小写字母。定义回文字符串为正序和逆序相同的字符串。求解比该字符串小(按照字典顺序)的回文字符串有多少个？(这个数字会很大，因此输出其对取模)

输入

第一行为T，测试的个数。
以下每个测试有2行，前一行为字符串长度N和字母数量K；
后一行是这个字符串S。

输出

输出格式为 Case #x: y，表示第x个测试(x从1编号)比该字符串小的回文字符串有y个。

数据范围

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

Test Set 1

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

Test Set 2

Time limit: 10 seconds.
1≤N≤.
1≤K≤26.

解法1 (基础)

对于长度为N的回文字符串，只需考虑前一半即长度范围在(N+1)/2的情况。
对于字符串的第0个字符，比'a'的ASCII码每大1个，就意味着后面从第1到(N+1)/2的下标范围字符任意取值都满足，因此第0个字符和S[0]不相等的情况下会产生(S[0]-'a')种可能的字符串。
而第0个字符和S[0]相等的情况下，考虑S[1]同样可以得到(S[1]-'a')*种可能的字符串。
以此类推，直到S[(N+1)/2-1]时，首先有S[(N+1)/2-1]-'a'种可能，然后在S[(N+1)/2-1]相等时，判断输入给定的字符串比这时候的回文字符串大小，如果输入更大的话，那么最后的结果再加1。
数据较大，需要使用long long的类型，最后输出的结果需要对取模。

#include <stdio.h>
typedef long long int64;

int64 power(int x, int y)
{
    int64 s = 1;
    while (y-- > 0)
        s *= x;
    return s;
}

int main()
{
    int t = 0;
    scanf("%d", &t);
    for (int c = 0; c < t; c++)
    {
        int m = 0, k = 0;
        scanf("%d %d", &m, &k);
        int n = (m + 1) >> 1;
        char s[100001];
        scanf("%s", s);
        int64 summer = 0;
        for (int i = 0; i < n; i++)
            summer += (int64)(s[n - i - 1] - 'a') * power(k, i);

        int ckpt = -1;
        for (int i = m - n - 1; i >= 0; i--)
            if (s[i] != s[m - i - 1])
            {
                ckpt = i;
                break;
            }
        if (ckpt >= 0)
            if (s[ckpt] < s[m - ckpt - 1])
                summer++;
        summer = summer % 1000000007;
        printf("Case #%d: %lld\n", c + 1, summer);
    }
    return 0;
}

按照这个算法，时间复杂度为O(n^2)，样例和第一个测试集可以通过，但是在第二个测试集上会TLE，因此还需要对时间进行优化。

解法2 (时间优化)

由于上面的算法在计算字符串的时候需要反复计算K的高次幂，而这期间K是不变的，因此采用秦久韶算法对K的次方进行优化，改写成多项式相乘然后再相加，同时在每一步相乘之前都对取模，这样时间复杂度可以减到O(n)。

#include <stdio.h>
typedef long long int64;
const int mod = 1e9 + 7;

int main()
{
    int t = 0;
    scanf("%d", &t);
    for (int c = 0; c < t; c++)
    {
        int m = 0, k = 0;
        scanf("%d %d", &m, &k);
        int n = (m + 1) >> 1;
        char s[100001];
        scanf("%s", s);
        int64 summer = 0;
        for (int i = 0; i < n; i++)
        {
            summer *= k;
            summer += s[i] - 'a';
            summer %= mod;
        }

        int ckpt = -1;
        for (int i = m - n - 1; i >= 0; i--)
            if (s[i] != s[m - i - 1])
            {
                ckpt = i;
                break;
            }
        if (ckpt >= 0)
            if (s[ckpt] < s[m - ckpt - 1])
                summer++;
        summer %= mod;
        printf("Case #%d: %lld\n", c + 1, summer);
    }
    return 0;
}

使用改进后的算法在两个测试集都可以通过。

括弧：还有一种更直观的理解方式，就是把这个K看做base，然后把字符串S看做K进制的数(K≤26)，只需要把S转换为10进制数即可快速得到求解。