Problem 3D 密码破译

Problem 3D 密码破译

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

Problem 3D 密码破译

时间限制:30 秒

空间限制:2048 MB

题目描述

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

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

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

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

image-20230504082913850

示例

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

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

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

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

输入格式

第一行一个整数 nn,表示词库的大小。

接下来 nn 行每行一个字符串,表示词库中的一个单词。

最后一行一个字符串 ss,是待破译的字符串。

输出格式

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

样例输入1

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

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

样例输出1

样例1解释

可能的语段如下所示:

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

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

样例输入2

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

样例2解释

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

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

数据范围

共两组测试数据。

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

第二组测试数据 40 分。

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

悬赏令第三周

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