题意：给出一个键盘，按键都是大写字母。给出一个目标单词和一个长度L。最大值或者最大长度都是100。现在随机按键盘，每个按键的概率相同。
敲击出一个长度为L的序列。求该序列中目标单词最多可能出现几次，期望出现几次。输出两者的差。
分析：概率题
先求最大次数。直接看该目标单词首尾最大重叠多长，暴力求解即可。然后通过除法运算求最多出现几次。
求期望涉及到一个Linearity of Expecation的知识，用中文形象的描述可以称之为“期望重组”。
期望重组
现有随机变量X，传统求X期望的方法是把X的每个取值乘以其概率再加和。
而现在我们要对X的每个取值进行重组。
例如，E(X)=sigma(xi*pi)。当X=xi时，我们把X看作是n个随机变量的和。pi是恰好和为xi时的概率。
这想当与是按照X的每种取值进行分类计算。
现在我们给出另外一种求法。
设这n个随机变量总共有M种不同的取值方法。
（如果这些随机变量相互独立，那么M=m1*m2*...*mn，mi表示第i个随机变量有多少种取值。）
我们对于每一个随机变量ai都把M种情况枚举一次，计算每种情况发生的概率乘以ai在该种情况下的取值，并加和。
最后把所有随机变量的加和再加和，就是我们要求的E(X)。
详细说明请google搜索linearity of expectation。
根据期望重组我们可以轻松求出单词出现的次数，我们先求出在总长度的每个位置出现目标单词的期望。当然出现次数只能是0或1。
再乘以可能出现位置的总数即可。
这其实相当于对每个可能出现单词的位置都枚举了整个长度L串的所有情况。
但因为对于一个位置，很多位的取值并不会影响该位置是否会出现目标单词，所以也不用进行分类直接把那些位的所有情况看成一个整体，概率为1。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define D(x) const int MAX_N = 105; const int MAX_KEY = 30; int key_len, word_len, tot_len; char keyboard[MAX_N], word[MAX_N]; int num[MAX_N]; void input() { scanf("%d%d%d", &key_len, &word_len, &tot_len); scanf("%s%s", keyboard, word); } bool ok(int a) { for (int i = a; i < word_len; i++) if (word[i] != word[i - a]) return false; return true; } int get_max_time(int overlap) { for (int i = 0; i < word_len; i++) if (num[word[i] - 'A'] == 0) return 0; if (tot_len < word_len) return 0; return 1 + (tot_len - word_len) / overlap; } void work() { fill_n(num, 26, 0); for (int i = 0; i < key_len; i++) num[keyboard[i] - 'A']++; int max_time = 0; int overlap = word_len; for (int i = 1; i < word_len; i++) { if (ok(i)) { overlap = i; break; } } max_time = get_max_time(overlap); double ans = 1; for (int i = 0; i < word_len; i++) ans *= num[word[i] - 'A'] * 1.0 / key_len; ans *= tot_len - word_len + 1; D(printf("%.3f ", ans)); D(printf("%d ", max_time)); printf("%.8f ", max_time - ans); } int main() { int t; scanf("%d", &t); int case_num = 0; while (t--) { case_num++; printf("Case #%d: ", case_num); input(); work(); } return 0; }