PROBLEM LINK:
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:
-
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:
-
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.
-
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.
-
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;
}