(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进制数即可快速得到求解。
