比赛场次 614
比赛名称 2024暑期C班集训4
比赛状态 已结束比赛成绩
开始时间 2024-07-04 08:00:00
结束时间 2024-07-04 12:00:00
开放分组 全部用户
注释介绍 3 + 1
题目名称 玩具
输入输出 toyy.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatarliuyiche AAATTTTTTT 7.000 s 4.36 MiB 30
Gravatar健康铀 AWWWWWWWWW 0.000 s 0.00 MiB 10
Gravatardjyqjy WWWTTTTTTT 7.050 s 5.16 MiB 0

玩具

★★★☆   输入文件:toyy.in   输出文件:toyy.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

这个故事发生在很久以前,在 IcePrincess_1968 和 IcePrince_  1968 都还在上幼儿园的时候。

IcePrince_1968 最近迷上了一种玩具,这种玩具中有两种零件:圆球和棍子。棍子的两头可以插在两个圆球上的各一个空洞中,从而将两个圆球连接起来。为了保证玩具的娱乐性,任意一个圆球上的空洞个数总是多于玩具套装中的棍子数。你可以认为圆球是没有体积的,所有棍子的长度均为 1。

IcePrince_1968 喜欢这样玩这种玩具:他先摸出玩具袋里的一个圆球放在地上,然后重复下面的操作 n-1 次:每次从袋中取出一个圆球和一根棍子,然后等概率的从地上的圆球中选择一个,将该圆球和选择的圆球用棍子连起来,使得新的圆球在选中圆球的正上方。

IcePrince_1968 对自己搭出的艺术品很满意,便决定把这个物品送给 IcePrincess_1968 作为生日礼物。然而生日礼物是需要包装的,因为默认圆球没有体积,所以 IcePrince_1968 不用考虑包装盒的长和宽,但是包装盒的高是需要确定的,这里我们假设 IcePrince_1968 是一个非常节俭的孩子,所以包装盒的高总是等于艺术品的高度。IcePrince_1968 想知道自己需要的包装盒的高的期望对质数 p 取模后的值,但他还在上幼儿园,怎么会算呢,于是就请你来帮助他。

【输入格式】

输入数据仅一行,包含两个正整数 n,p,表示最终的艺术品中圆球的个数和模数 p。

【输出格式】

输入文件仅一行,一个正整数,表示包装盒的高的期望对质数 p 取模后的值

【样例输入】

3 998244353

【样例输出】

499122178

【提示】

三个圆球组成的艺术品,高度只可能是 1 或者 2,所以高度的期望是 1.5,在模 998244353下的期望是 499122178

对于 30%的数据,满足 n<=10,p<=1,000,007;

对于 50%的数据,满足 n<=20;

对于 70%的数据,满足 n<=50;

对于 100%的数据,满足 n<=200,p<=1,000,000,007,p 是质数。

大洋里