Problem 3D 密码破译

Problem 3D 密码破译

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 3D 密码破译

时间限制:30 秒

空间限制:2048 MB

题目描述

对于一段由英文单词组成的语段 \(\{w_1,w_2,\cdots,w_n\}\)(\(w_i\) 是一个英文单词),以下流程可以称为"加密"。

  • 对于每个单词,将首字母转为大写,其他字母转为小写。
  • 将各个单词拼接,得到字符串 \(s\)。
  • 随机打乱 \(s\) 的各个字符。

例如,\(\{time,for,dinner\}\) 可以通过以下方法"加密"

  • 转换各个单词,并且拼接。即TimeForDinner
  • 随机打乱各个字符,例如转换为 FirminnoDTere

image-20230504082913850

示例

现在,给出一个词库 \(D\) 和待破译的字符串 \(s\),已知 \(s\) 是由某语段 \(\{w_1,w_2,\cdots,w_n\}\) 按以上方法 "加密" 得到的,并且每个 \(w_i\) 是词库 \(D\) 中的单词。由于原始语段 \(\{w_1,w_2,\cdots,w_n\}\) 的可能性比较多,很难唯一确定它。所以你只需要求出满足要求的语段\(\{w_1,w_2,\cdots,w_n\}\) 的数量。

两个语段 A,B 不同,当且仅当:

  • 存在单词 \(w\),使得它在 A 中的出现次数与 B 中的出现次数不同。

换言之,单词的顺序对于语段来说是不重要的,\(\{time,for,dinner\}\) 和 \(\{for,dinner,time\}\) 视为同一个语段。

输入格式

第一行一个整数 \(n\),表示词库的大小。

接下来 \(n\) 行每行一个字符串,表示词库中的一个单词。

最后一行一个字符串 \(s\),是待破译的字符串。

输出格式

仅一个整数,表示可能的原始语段数量。

样例输入1

注意,在样例中我们省略了词库,在实际测试的时候则不会省略。

7500
...(省略7500行,每行一个单词)
cairAergaeatAGniMkmae

样例输出1

3

样例1解释

可能的语段如下所示:

again america gate maker 
again america great make 
america area gate making 

加密前,语段是 \(\{make,america,great,again\}\)。其他两种虽然看不出太多意义,但是也应当被计入答案中。

样例输入2

7500
...(省略7500行,每行一个单词)
nhEreBarlfgiInnnurfnntSinamtoTtveieuM

样例2解释

原始语段是 'Buffer', 'Sharing', 'In', 'Multi', 'Tenant', 'Environment',但是也有数百种其他的可能。

我们不提供样例 2 的答案,并且将其作为第一组测试数据。

数据范围

共两组测试数据。

第一组测试数据 60 分,保证待破译的字符串为 nhEreBarlfgiInnnurfnntSinamtoTtveieuM。

第二组测试数据 40 分。

对于所有测试数据,\(n=7500\),词库是固定的 7500 个常用词(你可以在 https://wwgm.lanzouy.com/ilLRY0umqhxe 获取这个词库)。待破译的字符串的单词数不超过 \(6\),总长度不超过 \(40\),可能的原始语段数量不超过 \(10^5\)。

悬赏令第三周

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-05-08 17:00
结束于
2023-05-14 00:00
持续时间
127.0 小时
主持人
参赛人数
43