P4071 [SDOI2016]排列计数

    • 527通过
    • 934提交
  • 题目提供者 ElevenDimensions
  • 评测方式 云端评测
  • 标签 枚举,暴力 线性递推,递推式 逆元 递推 各省省选 2016 山东
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    求有多少种长度为 n 的序列 A,满足以下条件:

    1 ~ n 这 n 个数在序列中各出现了一次

    若第 i 个数 A[i] 的值为 i,则称 i 是稳定的。序列恰好有 m 个数是稳定的

    满足条件的序列可能很多,序列数对 $10^9+7$ 取模。

    输入输出格式

    输入格式:

    第一行一个数 T,表示有 T 组数据。

    接下来 T 行,每行两个整数 n、m。

    输出格式:

    输出 T 行,每行一个数,表示求出的序列数

    输入输出样例

    输入样例#1: 复制
    5
    1 0
    1 1
    5 2
    100 50
    10000 5000
    输出样例#1: 复制
    0
    1
    20
    578028887
    60695423

    说明

    测试点 1 ~ 3: $T = 1000 $,$ n \leq 8 $,$ m \leq 8 $;

    测试点 4 ~ 6: $T = 1000 $,$ n \leq 12 $,$ m \leq 12 $;

    测试点 7 ~ 9: $T = 1000 $,$ n \leq 100 $,$ m \leq 100 $;

    测试点 10 ~ 12:$ T = 1000 $,$ n \leq 1000 $,$ m \leq 1000 $;

    测试点 13 ~ 14:$ T = 500000 $,$ n \leq 1000 $,$ m \leq 1000 $;

    测试点 15 ~ 20:$ T = 500000 $,$ n \leq 1000000 $,$ m \leq 1000000 $。

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