P5337 [TJOI2019]甲苯先生的字符串

    • 141通过
    • 254提交
  • 题目提供者 ThomasX
  • 评测方式 云端评测
  • 标签 各省省选 2019 天津
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    TJOI2019 D1T1

    源文件名:str.*

    时间限制: 1s 内存限制: 128M

    题目描述

    一天小甲苯得到了一条神的指示,他要把神的指示写下来,但是又不能泄露天机,所以他要用一种方法把神的指示记下来。神的指示是一个字符串,记为字符串$s_1$,$s_1$仅包含小写字母a − z。现在小甲苯想要写下神的指示,记为字符串$s_2$,$s_2$仅包含小写字母a − z,要求$s_1$中的相邻的两个字母不能在$s_2$中相邻地出现。现在给定$s_2$的长度,小甲苯想知道他有多少种方法可以将神的指示写下来。输出种类数结果对$10^9+7$取模。

    输入输出格式

    输入格式:

    第一行只有一个正整数$n$,代表字符串$s_2$的长度,$n\le10^{15}$。

    第二行是一个字符串,代表字符串$s_1$。$s_1$的长度不超过$100000$。

    输出格式:

    输出一个整数,表示小甲苯可以写出的字符串的总数。结果对$10^9+7$取模

    输入输出样例

    输入样例#1: 复制
    2
    ab
    
    输出样例#1: 复制
    675
    

    说明

    对于30%的数据$n\le100000$

    对于100%的数据$n\le10^{15}$

    说明:相邻要求顺序相同,如样例中的$s_2$里不能出现$ab$,且仅不能出现$ab$,但可以出现$ba$.

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