Question Name:SUPER TWO LETTER STRINGS

#include<bits/stdc++.h>
using namespace std;
int main()
{
   long int i,j,dp[11][10001];
    for(i=1;i<=10;i++)
    {
        dp[i][0]=1;
        dp[i][1]=1;
        for(j=2;j<=10000;j++)
        {
            if(j>i)
               { 
                 dp[i][j]=(2*dp[i][j-1]-dp[i][j-i-1]+1000000007)%1000000007;
               }
            else
              {
                  dp[i][j]=(2*dp[i][j-1])%1000000007;
              }
        }
    }
    int t,n,p;
    cin>>t;
    while(t--)
    {
        cin>>n>>p;
        cout<<dp[p][n]<<endl;
    }
}
  • Problem Description
    Two letter strings are the strings consisting of only two letters “X” and “Y”. A string is “super two letter string” if

    a) It does not have leading “X” letters.
    b) It does not contain P consecutive “X” letters.
    Your task is to find total number of Super two letter strings of length N.

    Input :

    The first line contains the number of test cases T . Each test case consists of two space separated integers – N and P .

    Output :

    For each test case output total number of Super two letter strings of length N modulo 1000000007(10^9+7).

    Constraints :

    1 <= T <= 100
    1 <= N <= 10^4
    1 <= P <= 10
  • Test Case 1
    Input (stdin)2
    2 1
    4 2
    Expected Output1
    5
  • Test Case 2
    Input (stdin)7
    2 3
    1 4
    5 1
    6 3
    1 3
    4 2
    7 2
    Expected Output2
    1
    1
    24
    1
    5
    21

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.