Codeforces 150B Quantity of Strings
这道题是 Codeforces Round #107 (Div. 2) 中的 D 题。其题意是，给出 n, m, k 三个整数，问在字母表有 m 个元素的、长度为 n 的字符串中，存在多少个这样的字符串，其所有长度为 k 的子串是回文串。
一开始我理解错题意了，我当时以为是只要那个串含有回文子串，那么就把它算进去。其实我感觉还是挺傻的，因为长度为 1 的串也是回文串啊，那这样岂不是所有的都要算进去了？
这样的话问题就简单多了。首先考虑当 k > n 时，由于此时长度为 n 的串中，长度为 k 的子串是不存在的。可以这么说，这个子串的集合是空集。那么，我说 ∅ 中的任何一个元素，都是回文串，这是没有问题的吧。如果你觉得有问题，那你找一个不是回文串的元素出来看看呀？
（以下段落的存在是为了说明“空集中的任何一个元素都是回文串”。）
其实上面那种情况是一个逻辑问题，有的时候用代码来解释一些现象还是比较方便的。打个比方，0 的阶乘大家都知道应该是 1 吧，为什么是 1 呢？看代码：
1 2 3 4 5 6 7 | int frac(int n) { int r = 1; for (int i = 1; i <= n; ++i) r *= i; return r; } |
这是计算阶乘的代码，如果将 0 传给参数 n, 那么返回的值应该是 1.
好，那么如果有一个函数，可以判断集合 s 中，是不是每个元素都是回文串。那么代码应该这么写：
1 2 3 4 5 6 7 8 9 10 11 12 13 | bool is_palindrome(const string &n) { return whether_n_is_a_palindrome_string; } bool are_all_palindromes(const set<string> &s) { set<string>::iterator it; for (it = s.begin(); it != s.end(); ++it) if (!is_palindrome(*it)) return false; return true; } |
如果给 are_all_palindromes 的参数 s 传入的是空集，那么，上面的函数会返回 true. 所以，k > n 的时候，任何一个长度为 n 的串的长度为 k 的子串都是回文串。
（说明完毕。）
其它情况，当 k < n 的时候：如果 k 是偶数，那么那些所有元素都是一样的串才能符合要求；如果 k 是奇数但不是 1, 那么那些只有两种元素的串才能符合要求；如果 k 是 1 那么所有的串都符合要求。所以代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <iostream> using namespace std; inline int power(int a, int n) { long long result = 1; while (n--) result = (result * a) % 1000000007; return result; } int main() { int n, m, k; cin >> n >> m >> k; if (k == 1 || k > n) cout << power(m, n) << endl; else if (k == n) cout << power(m, (n + 1) >> 1) << endl; else if (k & 1) // k is odd. cout << m * m << endl; else // k is even. cout << m << endl; return 0; } |
[...] 0;}D 和 E 到时候再研究一下吧，要加油啊。2012 年 2 月 19 日更新：D 题 150B Quantity of Strings 的题解请点击这里。原创文章，转载请注明来源：http://euyuil.com/3254/codeforces-round-107-div-2/ [...]