A27715. 稳定串（stable）问题描述给定一个长度为n的01串，如果串中任意连续一段为1的子串长度都只为3，则称该串是稳定串，那么，对于长度为n的01串，要保证该01串为稳定串共有多少种方案？例如长度为7的01串中，0000000、1110000、0111000、1110111都是稳定串，而1011100、1111000、1111110则都不是稳定串。
填空题
中等
知识点
题目描述
稳定串（stable）
问题描述
给定一个长度为n的01串，如果串中任意连续一段为1的子串长度都只为3，则称该串是稳定串，那么，对于长度为n的01串，要保证该01串为稳定串共有多少种方案？
例如长度为7的01串中，0000000、1110000、0111000、1110111都是稳定串，而1011100、1111000、1111110则都不是稳定串。
输入格式
一行一个整数n，表示01串的长度。
输出格式
仅一行一个整数，表示长度为n的01串中稳定串的数量，由于数量可能很大，仅输出结果模10007的余数即可。
样例输入1
4
样例输出1
3
样例1解释
0000、1110、0111这3个是满足要求的稳定串。
样例输入2
7
样例输出2
7
样例2解释
000000、1110000、0111000、0011100、0001110、0000111、1110111这7个是满足要求的稳定串。
样例输入3
1718
样例输出2
2447
数据规模与约束
对于20%的数据，n≤100。
对于50%的数据，n≤10000。
对于100%的数据，n≤1000000。
参考答案
#include<bits/stdc++.h>
using namespace std;
int a[1000005]={0,1,1,2,3,4,5,7,10 14},n;
int main()
{
cin>>n;
for(int i=5;i<=n;i++)
{
a[i]=(a[i-1]+a[i-4])%10007;
}
cout<<a[n];
return 0;
}
上一题
下一题