#P17813. [ICPC 2019 Nanchang R] Summon
[ICPC 2019 Nanchang R] Summon
题目描述
LKMCFJ 想要施放一个法术以召唤巨龙。为此,她需要将 颗宝石摆放在地上,形成一个圆形的召唤环。她准备了 种不同的宝石:风、火、雷、电,每种宝石的数量都是无限的。
某些宝石的排列方式可能会发生爆炸,如果 LKMCFJ 不避开这些危险,她就会丧命。更确切地说,一些给定的沿顺时针方向连续 颗宝石的组合是不被允许的。
现在她想知道,基于这些限制,她能够制作出多少种不同的召唤环。注意,如果两个环通过旋转其中一个可以变得完全相同,则它们被视为同一种。
由于答案可能非常巨大,你只需要输出答案对 取模的结果。
输入格式
第一行输入包含两个整数 和 ,分别表示召唤环所需的宝石数量,以及会导致爆炸的长度为 的模式数量。
接下来的 行,每行包含 个整数,描述一个沿顺时针方向连续 颗宝石的、应当避免的模式。这里,我们分别用整数 来代表四种不同类型的宝石。
输出格式
在一行中输出一个整数,表示答案对 取模的结果。
4 3
0 1 2 3
1 2 3 1
2 1 3 0
67
提示
翻译由 DeepSeek V4 Pro 完成