(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 .

問(wèn)題簡(jiǎn)述

給定字符串長(zhǎng)度為N，僅包含字母表上的前K個(gè)小寫(xiě)字母。定義回文字符串為正序和逆序相同的字符串。求解比該字符串小(按照字典順序)的回文字符串有多少個(gè)？(這個(gè)數(shù)字會(huì)很大，因此輸出其對(duì)取模)

輸入

第一行為T(mén)，測(cè)試的個(gè)數(shù)。
以下每個(gè)測(cè)試有2行，前一行為字符串長(zhǎng)度N和字母數(shù)量K；
后一行是這個(gè)字符串S。

輸出

輸出格式為 Case #x: y，表示第x個(gè)測(cè)試(x從1編號(hào))比該字符串小的回文字符串有y個(gè)。

數(shù)據(jù)范圍

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 (基礎(chǔ))

對(duì)于長(zhǎng)度為N的回文字符串，只需考慮前一半即長(zhǎng)度范圍在(N+1)/2的情況。
對(duì)于字符串的第0個(gè)字符，比'a'的ASCII碼每大1個(gè)，就意味著后面從第1到(N+1)/2的下標(biāo)范圍字符任意取值都滿足，因此第0個(gè)字符和S[0]不相等的情況下會(huì)產(chǎn)生(S[0]-'a')種可能的字符串。
而第0個(gè)字符和S[0]相等的情況下，考慮S[1]同樣可以得到(S[1]-'a')*種可能的字符串。
以此類(lèi)推，直到S[(N+1)/2-1]時(shí)，首先有S[(N+1)/2-1]-'a'種可能，然后在S[(N+1)/2-1]相等時(shí)，判斷輸入給定的字符串比這時(shí)候的回文字符串大小，如果輸入更大的話，那么最后的結(jié)果再加1。
數(shù)據(jù)較大，需要使用long long的類(lèi)型，最后輸出的結(jié)果需要對(duì)取模。

#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;
}

按照這個(gè)算法，時(shí)間復(fù)雜度為O(n^2)，樣例和第一個(gè)測(cè)試集可以通過(guò)，但是在第二個(gè)測(cè)試集上會(huì)TLE，因此還需要對(duì)時(shí)間進(jìn)行優(yōu)化。

解法2 (時(shí)間優(yōu)化)

由于上面的算法在計(jì)算字符串的時(shí)候需要反復(fù)計(jì)算K的高次冪，而這期間K是不變的，因此采用秦久韶算法對(duì)K的次方進(jìn)行優(yōu)化，改寫(xiě)成多項(xiàng)式相乘然后再相加，同時(shí)在每一步相乘之前都對(duì)取模，這樣時(shí)間復(fù)雜度可以減到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;
}

使用改進(jìn)后的算法在兩個(gè)測(cè)試集都可以通過(guò)。

括?。哼€有一種更直觀的理解方式，就是把這個(gè)K看做base，然后把字符串S看做K進(jìn)制的數(shù)(K≤26)，只需要把S轉(zhuǎn)換為10進(jìn)制數(shù)即可快速得到求解。