题库 信息学奥赛题库 题目列表 稳定串(stable)【问题描述】给定一个长度为n的01串...
问答题

稳定串(stable

【问题描述】

给定一个长度为n01,如果串中任意连续一段为1子串都只为3,则称该串是稳定串,那么,对长度为n01证该01为稳定共有多少种方案?

例如长度为701中,0000000111000001110001110111稳定串,而101110011110001111110都不是稳定串。

【输入格式】

一行一个整数n表示01的长度。

【输出格式】

仅一行一个整数,表示长度n01中稳定串的数量,由于数量可能很大,仅输出结果模10007的余数即可

【样例输入1

4

【样例输出1

3

【样例1解释】

0000111001113个是满足要求的稳定串。

【样例输入2

7

【样例输出2

7

【样例2解释】

0000001110000011100000111000001110000011111101117个是满足要求的稳定串。

【样例输入3

1718

【样例输出2

2447

【数据规模与约束】

对于20%的数据,n≤100

对于50%的数据,n≤10000

对于100%的数据,n≤1000000

题目信息
完善程序 2021年 初赛
-
正确率
0
评论
153
点击