PROBLEM LINK
[Practice][1][Contest][2]
Author : Ankit Sagwekar
Tester : Vikesh Tiwari
Editorialist : Ankit Sagwekar
DIFFICULTY
EasyPREREQUISITES
basics,array,implementationPROBLEM
Given two integers 'm' and 'n'. Find the number of combinations of bitsize 'n' in which there are no 'm' consecutive '1'.
EXPLANATION
We are given with m and n. There are 3 cases for any given value of n and m

Case 1:
when n is less than m
for this the ans will be equal to ans=pow(2,n).
eg: 3 2
all the 2 bit words i.e 00 01 10 11 will not have 3 consecutive 1 ,thus all of them are selected. 
Case 2: when n is equal to m
for this the ans will be equal to ans=pow(2,n)1.
eg: 3 3
all the 3 bit words i.e 000 001 010 011 100 101 110 111 out of which only one word will have 3 consecutive ‘1’. 
Case 3: when n is more than m
This test case needs some computation which we will see through eg.
eg:
3 4
Here we first calculate for
m n
3 3 = 7
3 2 = 4
3 1 = 2
then adding this ,we get for 3 4 as 7+4+2=13.
here m=3 thus we calculate for 3 values and add them .
eg:4 6
here we first calculate for
m n
4 5 = 29
4 4 = 15
4 3 = 8
4 2 = 4
then adding this ,we get for 4 6 as 29+15+8+4=56.
here m=4 thus we calculated for 4 values and add them .
Note: for faster computation we can precompute all the values and can store them in 2D matrix.
Complexity:
(O(N^2.logN))C++ Code
#include <stdio.h>
#include<math.h>
int main(void) {
// your code goes here
long long int t,n,m,i,j,k,a[15][105],l;
scanf("%lld",&t);
for(i=2;i<=10;i++)
for(j=1;j<=50;j++)
{
if(j<i)
a*[j]=pow(2,j);
else if(j==i)
a*[j]=pow(2,j)1;
else
{
k=i;
l=j1;
while(k>0)
{ k;
a*[j]+=a*[l];
}
}
}
/*
for(i=2;i<=10;i++)
{
for(j=1;j<=50;j++)
{
printf("%lld ",a*[j]);
}
printf("
“);
}
*/
// you can uncomment the above section to see all the precomputed values
while(t–)
{
scanf(”%lld%lld",&m,&n);
printf("%lld
",a[m][n]);
}
return 0;
}