### 0/1 tiles problem. I need the mathematical soln for this.

Problem 1: 0/1 Tiles
To help Lavanya learn all about binary numbers and binary sequences, her father has bought her a collection of square tiles, each of which has either a 0 or a 1 written on it. Her brother Nikhil has played a rather nasty prank. He has glued together pairs of tiles with 0 written on them. Lavanya now has square tiles with 1 on them and rectangular tiles with two 0's on them, made up of two square tiles with 0 stuck together). Thus, she can no longer make all possible binary sequences using these tiles.
To amuse herself, Lavanya has decided to pick a number N and try and construct as many binary sequences of length N as possible using her collection of tiles. For example if N = 1, she can only make the sequence 1. For N=2, she can make 11 and 00. For N=4, there are 5 possiblities: 0011, 0000, 1001, 1100 and 1111.
Lavanya would like you to write a program to compute the number of arrangements possible with N tiles so that she can verify that she has generated all of them. Since she cannot count beyond 15746, it is sufficient to report this number modulo 15746.
Input format
A single line with a single integer N.
Output format
A single integer indicating the number of binary sequences of length N, modulo 15746, that Lavanya can make using her tiles.
Test data
You may assume that N ≤ 1000000.
Example
Here is a sample input and output corresponding to the example discussed above.
Sample input
4
Sample output
5

CPU Timelimit: 3 seconds
Memory limit: 64M

this is the problem. i need some mathematical logical answer behind it.
This is my take on it.

N = 1 -> Output = 1
N = 2 -> Output = 2
N = 3 -> Output = 3
N = 4 -> Output = 5
N = 5 -> Output = 8
N = 6 -> Output = 13
N = 7 -> Output = 21

I wrote the binary sequences down on some paper and figured out the first 5 possible values with the 0's glued together, then I tried to recognize a pattern, and to me it looks like the Fibonacci sequence. It is not very difficult to code the Fibonacci sequence:

 ``123456789101112131415161718192021222324252627282930`` ``````#include using namespace std; int compute(int n) { if (n <= 3) { return n; } else { return compute(n - 1) + compute(n - 2); } } int main() { int n; cout << "Input integer N: "; cin >> n; cin.ignore(); cout << "\nNumber of combinations: " << compute(n); cin.get(); return 0; }``````

I don't know about the rest of it (the mod 15746, not sure where that comes in). Maybe you can figure out the rest of it. I hope this is at least a little help. You probably know more about it than me since you were most likely in class.
Topic archived. No new replies allowed.