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}\)。

2023秋 悬赏令第三周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-10-22 18:30
结束于
2023-10-29 00:00
持续时间
149.5 小时
主持人
参赛人数
85