#PQJ463x2588. QOJ 463_2588

    ID: 2980 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:TJOI 2019字符串动态规划快速幂

QOJ 463_2588

NOI 2019天津市代表队选拔赛day1 注意 请各位参赛选手在E 盘根目录建立以自己文件夹号为名字的文件夹,文 件夹下建立以题目为名字的文件夹,源程序放在相应的题目文件夹下。例如 E:/TJ-001/roll/roll.cpp。除TJ 外其余字母均为小写。除源程序外,其余无关 文件不要放在该文件夹。 A 甲苯先生的字符串 • 输入输出文件: str.in/str.out • 源文件名: str.cpp/str.c/str.pas • 时间限制: 1s 内存限制: 128M 题目描述 一天小甲苯得到了一条神的指示,他要把神的指示写下来,但是又不能泄露 天机,所以他要用一种方法把神的指示记下来。神的指示是一个字符串,记为 字符串s1,s1仅包含小写字母a −z。现在小甲苯想要写下神的指示,记为字符 串s2,s2仅包含小写字母a −z,要求s1中的相邻的两个字母不能在s2中相邻地 出现。现在给定s2的长度,小甲苯想知道他有多少种方法可以将神的指示写下 来。输出种类数结果对109 + 7取模。 输入 文件的第一行只有一个正整数n,代表字符串s2的长度,n ≤1015。 第二行是一个字符串,代表字符串s1。s1的长度不超过100000。 输出 输出一个整数,表示小甲苯可以写出的字符串的总数。结果对109 + 7取模 样例输入1 2 ab 样例输出1 675 数据范围 对于30%的数据n ≤100000 对于100%的数据n ≤1015 2