Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:256 MB

#2874. 拯救创界山(mountain)

统计

【题目背景】:

Zm作为德智体美劳兼优的好学生,还精通算法之道,创界山这次沦陷在zzh的手下,上一届的救世主战部渡由于脑子不好使,只好找到了zm来作为新的创界山救世主,为了考研zm的智慧,小渡给他说了这样一个问题(见题面描述)来让他回答。

【题面描述】:

创界山一共由 $n$ 层组成,外层包裹着由 $m$ 种颜色组成的彩虹,每层有L[i]个村子分布在一条直线上,每个村子的所有人信仰彩虹的m种颜色的中的一种颜色(一个村子的所有人信仰同一种颜色),因为他们认为那种颜色是远古龙神的庇佑,如果两个相邻的村子信仰的颜色一样,两个村子的人就会傻傻分不清楚,所以任意两个相邻村子信仰的颜色都不一样,同样的,对于两个相邻的层,他们的信仰的颜色集合(如某一层为 $2,2,3,4,3$,那么集合为 ${2,3,4}$)一样的话,两层人民也会傻傻分不清楚。现在zm是救世主,他可以决定每一个村子的人该信仰哪种颜色,小渡只需要一种合法的方案(就是给每个村子分配该信仰那种颜色同时使得不会有人民傻傻分不清楚)就是了,这对于zm来说简直太容易了!然而他想考考你:一共有多少种合法的方案,由于方案太多,zm还给了你一个 $P$,让你将答案对 $P$ 取模?请编程解决这个问题。

【输入格式】:

输入到文件 mountain.in

第一行 $3$ 个数,$n,m,P$,意义见题面描述。

第二行 $n$ 个数,其中的第 $i$ 个表示 $L_i$,意义见题面描述。

【输出格式】:

输出到文件 mountain.out

一行,表示所有方案数 $\bmod P$ 的答案。

【样例输入1】:

2 3 1000
2 2

【样例输出1】:

24

【样例输入2】:

3 2 1000
3 1 2

【样例输出2】:

8

【数据范围】:

对于 $10\%$ 的数据,$m=1$; 对于另外 $10\%$ 的数据,$n=1$; 对于另外 $20\%$ 的数据,$m \leq 6$; 对于另外 $20\%$ 的数据,对于任意的 $1 \leq i < n$,都有 $L_i \times L_{i+1} = L_i + L_{i+1} - 1 $ ; 对于 $100\%$ 的数据,$1 \leq n,m \leq 10^6,1 \leq P \leq 10^9,1 \leq L_i \leq 5 \times 10^3$ 且所有 $L_i$ 加起来不会超过 $10^7$。