TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7611
  • 题目
  • P7611[CF1439D] Final Contests
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 3s,256MB
    问题描述

    今天机房将举办一场考试。机房有$n$台电脑排成一排,从左到右电脑编号依次为$1$到$n$。有$m$个参与者,编号为$1$到$m$的整数。

    我们有一个长度为$n$的数组$a$,其中$a_i$($ 1\leqslant a_i \leqslant n$)是第$i$个参赛者希望坐的电脑的编号。

    我们还有一个长度为$m$的数组$b$,表示参赛者入场的方向,由字符$L$和$R$组成。如果$b_i$为$L$那么表示$i$号参赛者从$1$号电脑的左侧进入考场并向右走,$b_i$为$R$那么表示$i$号参赛者从$n$号电脑的右侧进入考场并向左走。

    参赛者按$1$到$m$的顺序依次进入房间,第$i$个人延$b_i$方向进入机房,然后坐在第$a_i$台电脑处。如果已经被占用,他将继续延自己的方向走直到到达第一台未被占用的电脑然后坐下。如果他找不到任何未被占用的电脑,他会感到沮丧并放弃本场考试。

    第$i$个参赛者的失望程度定义为他实际使用的电脑与他希望使用的电脑的距离。第$i$台电脑与第$j$台电脑之间的距离定义为$ \ |i-j|$。

    $a$数组中的元素可以相等。存在 \(n^m\times2^m\) 个可能的数组对 \((a,b)\)

    对于所有不会使人感到沮丧的成对的数组$(a,b)$,计算所有参赛者的失望程度的总和。

    你将得到一个模数$p$($p$为质数),答案对$p$取模。

    输入格式

    唯一的一行包含三个整数$n$,\(m\),\(p\)( $1 \leqslant m \leqslant n\leqslant 500$ , \(\qquad10^7+9 \leqslant p \leqslant 10^9+7\)

    输出格式

    仅输出一个整数:失望值总和,对$p$取模。

    样例输入 1

    3 1 1000000007

    样例输出 1

    0

    样例输入 2

    2 2 1000000009

    样例输出 2

    4

    样例输入 3

    3 2 998244353

    样例输出 3

    8

    样例输入 4

    20 10 1000000009

    样例输出 4

    352081045

    提示

    感谢playerzmr翻译并提供官方数据


    来源  感谢playerzmr翻译并提供官方数据