#2205. Constructing a coloring

    ID: 2205 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1655来源:qoj.ac数据:公开样例数学组合数学

Constructing a coloring

Constructing a coloring

题目描述

标题: Constructing a coloring - Problem - QOJ.ac

#16216. Constructing a coloring

Statistics

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

  1. (10分)n≤10,m≤4
  2. (20分)n≤100
  3. (30分)n≤50000
  4. (20分)m≤106
  5. (20分)无特殊限制。

Sample Grader

样例交互器以下列格式读取输入。

  • 一行:n m p

样例交互器以下列格式打印你的输出。

  • 一行,你的返回值

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 2 998244353
6

样例 2

100 12345 998244353
318055149