P3757 [CQOI2017]老C的键盘

    • 121通过
    • 208提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 前缀和 动态规划,动规,dp 树形动规 线段树 各省省选 2017 重庆
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    老C是个程序员。

    作为一个优秀的程序员,老C拥有一个别具一格的键盘,据说这样可以大幅提升写程序的速度,还能让写出来的程序在某种神奇力量的驱使之下跑得非常快。

    小Q也是一个程序员。有一天他悄悄潜入了老C的家中,想要看看这个键盘究竟有何妙处。他发现,这个键盘共有n个按键,这n个按键虽然整齐的排成一列,但是每个键的高度却互不相同。聪明的小Q马上将每个键的高度用1~n的整数表示了出来,得到一个1~n的排列$h_1,h_2,...,h_n$。

    为了回去之后可以仿造一个新键盘(新键盘每个键的高度也是一个1~n的排列),又不要和老C的键盘完全一样,小Q决定记录下若干对按键的高度关系。作为一个程序员,小Q当然不会随便选几对就记下来,而是选了非常有规律的一些按键对:对于$i=2,3,...,n$,小Q都记录下了一个字符<或者>,表示$h_{i/2}<h_i$或者$h_{i/2}>h_i$。于是,小Q得到了一个长度为n-1的字符串,开开心心的回家了。

    现在,小Q想知道满足他所记录的高度关系的键盘有多少个。虽然小Q不希望自己的键盘和老C的完全相同,但是完全相同也算一个满足要求的键盘。答案可能很大,你只需要告诉小Q答案mod 1,000,000,007之后的结果即可。

    输入输出格式

    输入格式:

    输入共1行,包含一个正整数n和一个长度为n-1的只包含<和>的字符串,分别表示键盘上按键的数量,和小Q记录的信息,整数和字符串之间有一个空格间隔。

    输出格式:

    输出共1行,包含一个整数,表示答案mod 1,000,000,007后的结果。

    输入输出样例

    输入样例#1: 复制
    5 <>><
    输出样例#1: 复制
    3
    输入样例#2: 复制
    5 <<<<
    输出样例#2: 复制
    8
    输入样例#3: 复制
    5 <<>>
    输出样例#3: 复制
    18

    说明

    【输入输出样例 1 说明】 共5个按键,第1个按键比第2个按键矮,第1个按键比第3个按键高,第2个按键比第4个

    按键高,第2个按键比第5个按键矮。

    这5个按键的高度排列可以是 (2,4,1,3,5) , (3,4,1,2,5) , (3,4,2,1,5) 。

    【输入输出样例 2 说明】

    这5个按键的高度排列可为 (1,2,3,4,5) , (1,2,3,5,4) , (1,2,4,3,5) , (1,2,4,5,3) , (1,2,5,3,4) ,

    (1,2,5,4,3) , (1,3,2,4,5) , (1,3,2,5,4) 。

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