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.

Powered By
CHP Adblock Detector Plugin | Codehelppro