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 HintWe 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
这道题我纯粹是靠列出一些数字找规律的。。。
#include#include #include using namespace std; const int mod = 9997; int a[10005] = {0,2,4,7,12}; int main() { int i; for(i = 5; i<=10000; i++) a[i] = (a[i-1]+a[i-2]+a[i-4])%mod; while(~scanf("%d",&i),i!=-1) printf("%d\n",a[i]); return 0; }