Description
You know YaoYao is fond of his chains. He has a lot of chains and each chain has n diamonds on it. There are two kinds of diamonds, labeled 0 and 1. We can write down the label of diamonds on a chain. So each chain can be written as a sequence consisting of 0 and 1.
We know that chains are different with each other. And their length is exactly n. And what’s more, each chain sequence doesn’t contain “101” as a substring.
Could you tell how many chains will YaoYao have at most?
We know that chains are different with each other. And their length is exactly n. And what’s more, each chain sequence doesn’t contain “101” as a substring.
Could you tell how many chains will YaoYao have at most?
Input
There will be multiple test cases in a test data. For each test case, there is only one number n(n<10000). The end of the input is indicated by a -1, which should not be processed as a case.
Output
For each test case, only one line with a number indicating the total number of chains YaoYao can have at most of length n. The answer should be print after module 9997.
Sample Input
3
4
-1
Sample Output
7
12
Hint
We can see when the length equals to 4. We can have those chains: 0000,0001,0010,0011 0100,0110,0111,1000 1001,1100,1110,1111
有一串由n个珠子连成的链 每个珠子的标号只能是 0或1 求总共有多少种不同的排列
一开始还在想是不是要用到位运算 没想到竟然是递推= =
#include<cstdio>
#include<iostream>
#include<bitset>
#include<algorithm>
using namespace std;
int a[10000+10];
int main()
{
int n;
int i,j;
a[0]=1;
a[1]=2;
a[2]=4;
a[3]=7;
a[4]=12;
for(i=5;i<=10000;i++)
{
a[i]=(a[i-1]+a[i-2]+a[i-4])%9997;
}
while(scanf("%d",&n)!=EOF)
{
if(n==-1) break;
printf("%d
",a[n]);
}
return 0;
}