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了，可以的话，请您参考添加页面，与大家一起分享你的题解！