P4981 父子

    • 400通过
    • 1.8K提交
  • 题目提供者 xnzy
  • 评测方式 云端评测
  • 标签 卡特兰,Catalan 生成树
  • 难度 提高+/省选-
  • 时空限制 1000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    上演在各大学男生寝室的日常 $:$

    $A :$ “我没带纸,快来厕所救我!”

    $B :$ “叫爸爸。”

    $A :$ “爸爸!”

    $............................................$

    $A :$ “我没钱了,能借我点吗。”

    $B :$ “叫爸爸。”

    $A :$ “爸爸!”

    一个月后、

    $B :$ “能把钱还给我吗。”

    $A :$ “叫爸爸。”

    $B :$ “爸爸!”

    题目描述

    对于全国各大大学的男生寝室,总是有各种混乱的父子关系。

    那么假设现在我们一个男生寝室有不同的 $n$ 个人,每个人都至多有一个“爸爸”,可以有多个“儿子”,且有且只有一个人没有“爸爸”(毕竟是室长,还是要给点面子,当然了,室长人人当嘛)。

    那么现在问题来了,对于一个有 $n$ 个人的寝室,最多可能存在多少种父子关系,当然每个人之间都必须要有直接或间接的父子关系。

    输入输出格式

    输入格式:

    第一行一个 正整数 $t$,表示有组数据。

    接下来 $t$ 行,每行一个整数 $n$,表示有 $n$ 个人。

    输出格式:

    共 $t$ 行,每行一个整数,求关系个数。

    由于答案可能较大,则我们需要输出答案对 $1e9+9$ 取模的值。

    输入输出样例

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

    说明

    • 对于 $10\%$ 的数据,保证 $t=0$;

    • 另有 $30\%$ 的数据,保证 $n≤5$;

    • 对于 $100\%$ 的数据,$t≤10^4$,$n≤10^9$。

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