TOSSOT - EDITORIAL

PROBLEM LINK:

Contest

Practice

Author: Hardik Shah

Editorialist: Aishwarya


DIFFICULTY:

EASY.


PREREQUISITES:

Math, Combinatorics.


PROBLEM:

You are given the number of total tosses and number of times heads occured.

You are required to find number of strings that give a palindromic toss result.


EXPLANATION:

Firstly we need to split the string in 2 halves. This eases the process of finding palindromes, because if one half of the string is fixed, we can replicate the same as the 2nd half to make the string palindromic.

There can be four cases:

  1. N is odd, K is odd : On splitting th string in 2 halves and keeping a HEAD at the center of the string, we need to decide positions for half of the heads in the string, thus:

  2. N is odd, K is even : On splitting th string in 2 halves and keeping a TAIL at the center of the string, we need to decide positions for half of the heads in the string.

  3. N is even, K is even: On splitting the string in 2 halves, we need to decide positions for half of the heads in the string.

  4. N is even, K is odd: No solution exists, as there is no way to place odd number of heads in a string of even size to get a palindrome.

In first 3 cases:

No of unique palindrome strings = \dbinom{\lfloor \frac {n} {2} \rfloor}{\lfloor \frac {k} {2} \rfloor}


SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

#define ll long long

const int N = 1000001;

using namespace std;

 

ll factorialNumInverse[N + 1];

ll naturalNumInverse[N + 1];

ll fact[N + 1];

void InverseofNumber(ll p)

{

    naturalNumInverse[0] = naturalNumInverse[1] = 1;

    for (int i = 2; i <= N; i++)

        naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;

}

void InverseofFactorial(ll p)

{

    factorialNumInverse[0] = factorialNumInverse[1] = 1;

    for (int i = 2; i <= N; i++) factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;

}

 

void factorial(ll p)

{

    fact[0] = 1;

 

    for (int i = 1; i <= N; i++) {

        fact[i] = (fact[i - 1] * i) % p;

    }

}

 

// Function to return nCr % p in O(1) time

ll Binomial(ll N, ll R, ll p)

{

    // n C r = n!*inverse(r!)*inverse((n-r)!)

    ll ans = ((fact[N] * factorialNumInverse[R])

              % p * factorialNumInverse[N - R])

             % p;

    return ans;

}

 

// Driver Code

int main()

{

    ll p = 1000000007;

    InverseofNumber(p);

    InverseofFactorial(p);

    factorial(p);

 

    // 1st query

    int tt; cin >> tt;

   

    while(tt--)

    {

        int n, r; cin >> n >> r;

        if(n%2 == 0 && r%2) cout << 0 << "\n";

        else cout << Binomial(n/2, r/2, p) << "\n";

    }

 

    return 0;

}