Problem 3D 密码破译
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 3D 密码破译
时间限制:30 秒
空间限制:2048 MB
题目描述
对于一段由英文单词组成的语段 ( 是一个英文单词),以下流程可以称为"加密"。
- 对于每个单词,将首字母转为大写,其他字母转为小写。
- 将各个单词拼接,得到字符串 。
- 随机打乱 的各个字符。
例如, 可以通过以下方法"加密"
- 转换各个单词,并且拼接。即TimeForDinner
- 随机打乱各个字符,例如转换为 FirminnoDTere
示例
现在,给出一个词库 和待破译的字符串 ,已知 是由某语段 按以上方法 "加密" 得到的,并且每个 是词库 中的单词。由于原始语段 的可能性比较多,很难唯一确定它。所以你只需要求出满足要求的语段 的数量。
两个语段 A,B 不同,当且仅当:
- 存在单词 ,使得它在 A 中的出现次数与 B 中的出现次数不同。
换言之,单词的顺序对于语段来说是不重要的, 和 视为同一个语段。
输入格式
第一行一个整数 ,表示词库的大小。
接下来 行每行一个字符串,表示词库中的一个单词。
最后一行一个字符串 ,是待破译的字符串。
输出格式
仅一个整数,表示可能的原始语段数量。
样例输入1
注意,在样例中我们省略了词库,在实际测试的时候则不会省略。
样例输出1
样例1解释
可能的语段如下所示:
加密前,语段是 。其他两种虽然看不出太多意义,但是也应当被计入答案中。
样例输入2
样例2解释
原始语段是 'Buffer', 'Sharing', 'In', 'Multi', 'Tenant', 'Environment',但是也有数百种其他的可能。
我们不提供样例 2 的答案,并且将其作为第一组测试数据。
数据范围
共两组测试数据。
第一组测试数据 60 分,保证待破译的字符串为 nhEreBarlfgiInnnurfnntSinamtoTtveieuM。
第二组测试数据 40 分。
对于所有测试数据,,词库是固定的 7500 个常用词(你可以在 https://wwgm.lanzouy.com/ilLRY0umqhxe 获取这个词库)。待破译的字符串的单词数不超过 ,总长度不超过 ,可能的原始语段数量不超过 。