Skip to content

14260: 【原4260】憨憨接龙

题目

题目描述

author: zzx 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4260

问题描述

​ 铁憨憨(TieHanHan)是SJTU的一名学生,他有一个哥哥,名叫金憨憨(JinHanHan)。

​ 国庆期间,铁憨憨听说ACM班要出机考题,于是他和金憨憨想了三天三夜,终于出了一道题。

​ 铁憨憨和金憨憨都很喜欢词语接龙,因此希望你能和他们一起玩。值得注意的是,铁憨憨和金憨憨不会说普通话,只会说憨憨语。

​ 憨憨语是由十六进制数构成的,每一个汉字都会对应憨憨语里的一个2位十六进制数。例如“亦”对应“00”,“可”对应“AE”,“赛”对应82,艇对应“11”。因此,如果他们想说“亦可赛艇”,他们就会说“00AE8211”;由于憨憨语的字符集太小了,因此会有多个汉字对应同一个2位十六进制数的情况。例如,“发”也对应“11”,和“艇”一样。如果他们想说“发大财”,他们就会说“114822”。

​ 铁憨憨一口气说出了n个词语(当然都是以憨憨语的形式),然后他定义词语A能够被词语B接上,当且仅当A的最后一个字(最后一个2位十六进制数)和B的第一个字(第一个2位十六进制数)相等。例如“00AE8211”后面可以接上“114822”,但是反过来显然不行。

​ 现在,金憨憨希望你能通过重新排列铁憨憨说出的第2~n-1个词语(即保持第一个和最后一个词语的位置不变,其它任意调换顺序),使得这n个词语中的每一个词语都能被它的下一个接上,从而形成一个完整的有n个词语的接龙。你需要做的事,就是告诉金憨憨有多少种可行的排列方案

​ 这时,铁憨憨和金憨憨的父亲憨憨王(HanHanKing)来了。憨憨王看了一眼题目,说:“如果把每个词语对应于有向图的一个顶点,顶点 a 到顶点 b 存在有向边当且仅当 a 对应的词语的最后一个字和 b 对应的词语的第一个字相同,这不就是求1到n的哈密顿路径条数吗?这不是NP完全问题吗?这能做?”

​ 铁憨憨:“能做,ACM班的人都超厉害。”

输入格式

第 1 行两个整数 n,p,其中 n 表示铁憨憨说出词语的数量,p 表示模数。

接下来 n 行,每行一个十六进制数字,即铁憨憨说出的所有词语,仅包含 0~9,A~F,最少 2 个字符,最多 10 个字符。保证词语两两不同。

输出格式

输出一行一个整数,表示排序的方案数。方案数可能很大,你只需输出答案除以 p 的余数。

样例输入

6 998244353
00AE8211
114822
22AA11
11EE33
33CD22
22AB34

样例输出

2

样例解释

样例的6个词语翻译成普通话分别为“亦可赛艇”,“发大财”,“见着风”,“是得雨”,“图森破”,“拿衣服”

有 2 种可行的方案:

1、00AE8211,114822,22AA11,11EE33,33CD22,22AB34

2、00AE8211,11EE33,33CD22,22AA11,114822,22AB34

数据规模

对于5%的数据,$n\le 10$

对于10%的数据,$n\le 15$

对于15%的数据,$n\le 20$

对于30%的数据,$ n\le100 $

对于75%的数据,$ n\le2,000 $

对于所有数据,$n\le 100,000$,$p=998244353$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!