P4982 规划

    • 26通过
    • 473提交
  • 题目提供者 hdxrie
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 期望 构造 O2优化
  • 难度 省选/NOI-
  • 时空限制 1000ms / 8MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    经过长期的艰苦奋斗,${\rm TimeTraveller\ }$终于成功进入了理想的学校。

    题目描述

    作为吃货的${\rm \ TimeTraveller}$,入学的第一件事不是去报到,而是去食堂调查菜品。但是由于各种原因,本学期食堂的菜品很少,而且食堂制定了几天的菜谱,那么这个学期里,以后每天提供的菜品都会按照菜谱轮流循环进行。听到这件事,${\rm TimeTraveller\ }$的内心当然是崩溃的,但是他还是希望每天能吃的不那么重复,于是${\rm \ TimeTraveller\ }$决定只要和前一天吃的菜不重复就行了,但是身为吃货的${\rm \ TimeTraveller\ }$当然也不想饿肚子,所以每天至少都要吃一道菜

    ${\rm TimeTraveller\ }$想要知道他有多少种合法的规划方案,但是他发现这实在是太多了,于是他来求助你,希望你能编写一个程序帮他计算。

    输入输出格式

    输入格式:

    第一行三个正整数$n,m,k$,分别表示这个学期有$n$天,总共有$m$种菜品,学校制定了$k$天的菜谱(所有菜品从$1$到$m$编号,保证$n ≥ k$)。

    接下来$k$行,每行第一个数$p$表示这一天学校准备了$p$道菜,紧接着有$p$个数,表示这一天的$p$道菜分别是哪几道(保证$p$不会超过$m$,且这$p$个数都是不重复的)。

    输出格式:

    输出合法方案的数量,由于答案可能过大,你只需要输出答案对$1e9+7$取模后的值。

    输入输出样例

    输入样例#1: 复制
    3 3 2
    2 1 3
    2 2 3
    
    输出样例#1: 复制
    11
    输入样例#2: 复制
    10 7 3
    5 1 2 3 4 5
    3 1 3 7
    4 1 2 6 7
    
    输出样例#2: 复制
    730285459

    说明

    样例$1$解释:

    方案$1$:第一天吃$1,3$号菜品,第二天吃$2$号菜品,第三天吃$1,3$号菜品;

    方案$2$:第一天吃$1,3$号菜品,第二天吃$2$号菜品,第三天吃$3$号菜品;

    方案$3$:第一天吃$1,3$号菜品,第二天吃$2$号菜品,第三天吃$1$号菜品;

    方案$4$:第一天吃$3$号菜品,第二天吃$2$号菜品,第三天吃$1,3$号菜品;

    方案$5$:第一天吃$3$号菜品,第二天吃$2$号菜品,第三天吃$3$号菜品;

    方案$6$:第一天吃$3$号菜品,第二天吃$2$号菜品,第三天吃$1$号菜品;

    方案$7$:第一天吃$1$号菜品,第二天吃$2,3$号菜品,第三天吃$1$号菜品;

    方案$8$:第一天吃$1$号菜品,第二天吃$3$号菜品,第三天吃$1$号菜品;

    方案$9$:第一天吃$1$号菜品,第二天吃$2$号菜品,第三天吃$1,3$号菜品;

    方案$10$:第一天吃$1$号菜品,第二天吃$2$号菜品,第三天吃$3$号菜品;

    方案$11$:第一天吃$1$号菜品,第二天吃$2$号菜品,第三天吃$1$号菜品。

    数据范围:

    • 对于$20\%$的数据,$n≤ 5,m≤ 7,k≤ 5$;

    • 对于$45\%$的数据,$n≤ 50000,m≤ 7,k≤ 7$;

    • 另有$10\%$的数据,$n≤ 10^7,m≤ 2,k= 1$;

    • 对于$70\%$的数据,$n≤ 10^7,m≤ 7,k≤ 7$;

    • 对于$100\%$的数据,$n≤ 10^7,m≤ 7,k≤ 300$。

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