(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個小寫字母。定義回文字符串為正序和逆序相同的字符串榄鉴。求解比該字符串小(按照字典順序)的回文字符串有多少個轰坊？(這個數(shù)字會很大跺撼，因此輸出其對取模)
輸入
第一行為T敛摘，測試的個數(shù)。
以下每個測試有2行习贫，前一行為字符串長度N和字母數(shù)量K逛球；
后一行是這個字符串S。
輸出
輸出格式為 Case #x: y苫昌，表示第x個測試(x從1編號)比該字符串小的回文字符串有y個颤绕。
數(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ǔ))
對于長度為N的回文字符串，只需考慮前一半即長度范圍在(N+1)/2的情況祟身。
對于字符串的第0個字符奥务，比'a'的ASCII碼每大1個，就意味著后面從第1到(N+1)/2的下標(biāo)范圍字符任意取值都滿足袜硫，因此第0個字符和S[0]不相等的情況下會產(chǎn)生(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]相等時闯睹，判斷輸入給定的字符串比這時候的回文字符串大小，如果輸入更大的話担神，那么最后的結(jié)果再加1楼吃。
數(shù)據(jù)較大，需要使用long long的類型妄讯，最后輸出的結(jié)果需要對取模孩锡。
#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;
}
按照這個算法，時間復(fù)雜度為O(n^2)捞挥，樣例和第一個測試集可以通過浮创，但是在第二個測試集上會TLE，因此還需要對時間進(jìn)行優(yōu)化砌函。
解法2 (時間優(yōu)化)
由于上面的算法在計算字符串的時候需要反復(fù)計算K的高次冪斩披，而這期間K是不變的，因此采用秦久韶算法對K的次方進(jìn)行優(yōu)化讹俊，改寫成多項(xiàng)式相乘然后再相加垦沉，同時在每一步相乘之前都對取模，這樣時間復(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)后的算法在兩個測試集都可以通過厕倍。
括弧：還有一種更直觀的理解方式贩疙，就是把這個K看做base讹弯，然后把字符串S看做K進(jìn)制的數(shù)(K≤26)况既，只需要把S轉(zhuǎn)換為10進(jìn)制數(shù)即可快速得到求解。
