#2205. Constructing a coloring
Constructing a coloring
Constructing a coloring
题目描述
标题: Constructing a coloring - Problem - QOJ.ac
#16216. Constructing a coloring
The problem was used in the following contests:
鲍勃发现了一个新的有趣的游戏。在这个游戏中,鲍勃有 n 个敌人要打,而每个敌人都有 m 种颜色之一的颜色。在一个回合中,鲍勃可以攻击一段连续的敌人,这些敌人必须有相同的颜色。
鲍勃想尽可能多地攻击敌人,但有时他并不满足。对于每一种颜色的设定,我们称鲍勃的幸福感为他在一个回合中可以攻击的最大数量的敌人。鲍勃想知道对于所有 mn 种可能的敌人颜色设置,他的幸福感之和。由于这个数字可能很大,你需要输出它对一个给定素数取模的结果。
Implementation Details
你应该包含 coloring.h,并实现如下过程:
int totalhappy(int n, int m, int p)
- n: 敌人的数量。
- m: 总颜色数。
- p: 模数。一个质数。
- 你实现的过程会被调用恰好一次。
- 你应该返回所有上色方案的幸福感之和对 p 取余的值:一个 [0,p−1] 的整数。
Example
考虑如下调用:totalhappy(2, 2, 998244353)
如果两个敌人颜色相同,鲍勃的幸福感为 2,否则为 1。因此,总幸福感为 2+2+1+1=6。一个正确的程序应该返回 6mod998244353=6。
Constraints
1≤n≤106
1≤m≤109
108<p<109,p 为质数。
Subtasks
- (10分)n≤10,m≤4
- (20分)n≤100
- (30分)n≤50000
- (20分)m≤106
- (20分)无特殊限制。
Sample Grader
样例交互器以下列格式读取输入。
- 一行:n m p
样例交互器以下列格式打印你的输出。
- 一行,你的返回值
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 2 998244353
6
样例 2
100 12345 998244353
318055149