Problem 3C. 彩带染色
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 3C. 彩带染色
题目描述
请希望用 \(k\) 种颜色染色一条彩带,彩带可分为 \(n\) 小段。
请找出满足以下条件的染色方案数量。
- 彩带的每一小段恰被染成这 \(k\) 种颜色中的一种。
- 相邻的两段不能染同一颜色,即对于 \(1\le i< n\),第 \(i\) 段彩带的颜色和第 \(i + 1\) 段彩带的颜色不同。
由于答案过大,请对 \(p\) 取模。
输入格式
三个正整数 \(k, n, p\),表示颜色种数、彩带长度、模数。
输出格式
仅一个非负整数,表示染色数量。由于答案过大,请对 \(p\) 取模。
样例输入1
3 3 5
样例输出1
2
样例1解释
共有 12 种染色方案,如下:
[1, 2, 1] [1, 2, 3] [1, 3, 1] [1, 3, 2]
[2, 1, 2] [2, 1, 3] [2, 3, 1] [2, 3, 2]
[3, 1, 2] [3, 1, 3] [3, 2, 1] [3, 2, 3]
故输出 \(12\bmod 5=2\)
样例输入 2
19 2004 37
样例输出 2
11
样例输入 3
31415926535897932 38462643383279502 88419716939937510
样例输出 3
83030957998744842
数据范围及约定
本题共 \(120\) 分。
测试点编号 | 约定 | 测试点分值 |
---|---|---|
1~3 | \(1\le k,n,p\le 5\) | 每个测试点 \(10\) 分 |
4~6 | \(n=2\) | 每个测试点 \(10\) 分 |
7~9 | \(p = 998244353\) | 每个测试点 \(10\) 分 |
10~12 | 无特殊约定 | 每个测试点 \(10\) 分 |
对于 \(100\%\) 的数据,\(1\le k,n,p\le 10^{18}\)。