P3214 [HNOI2011]卡农

    • 280通过
    • 530提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 数论,数学 组合数学 逆元 2011 湖南
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    众所周知卡农是一种复调音乐的写作技法,小余在听卡农音乐时灵感大发,发明了一种新的音乐谱写规则。他将声音分成 n 个音阶,并将音乐分成若干个片段。音乐的每个片段都是由 1 到 n 个音阶构成的和声,即从 n 个音阶中挑选若干个音阶同时演奏出来。为了强调与卡农的不同,他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性,他还规定在一段音乐中每个音阶被奏响的次数为偶数。现在的问题是:小余想知道包含 m 个片段的音乐一共有多少种。两段音乐 a 和 b 同种当且仅当将 a 的片段重新排列后可以得到 b。例如:假设 a

    为{{1,2},{2,3}},b 为{{3,2},{2,1}},那么 a 与 b 就是同种音乐。由于种数很多,你只需要

    输出答案模 100000007(质数)的结果。

    输入输出格式

    输入格式:

    从文件input.txt中读入数据,输入文件仅一行,具体是用空格隔开的两个正整数n和m,分别表示音阶的数量和音乐中的片段数。20%的数据满足n,m≤5,50%的数据满足n,m≤3000,100%

    的数据满足n,m≤1000000。

    输出格式:

    输出文件 output.txt 仅包含一个非负整数,表示音乐的种数模 100000007 的结果。【输入输出样例】

    输入输出样例

    输入样例#1: 复制
    2 3
    输出样例#1: 复制
    1

    说明

    样例解释:音乐为{{1},{2},{1,2}}

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。