HackerRank Combinatorics – Count Fox Sequences

Challenge: Count Fox Sequences

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464746086

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/count-fox-sequences/problem

Cerinta

A non-decreasing sequence is a called a **Fox** sequence, iff the most frequent element in the sequence is unique. 

e.g. The sequence `1, 1, 2, 3, 4`  is a **Fox** sequence, because it follows the above definition. The most frequent element is 1. It occurs twice in the series, and is unique.

But the sequence `1, 1, 2, 2` is _not_ a **Fox** sequence, because there are two most frequent elements - 1 and 2. It violates the uniqueness property.

**Note**: Sequence `2, 1, 1` is not a **Fox** sequence, because it is not a non-decreasing sequence.

You need to find the number of all possible **Fox** sequences of length _n_ with elements having value between _lo_ and _hi_ inclusive.  

As the number can grow very large, return the number modulo (_10<sup>9</sup> + 7_).

**Input Format**  
The first line will contain _T_, i.e., the number of test cases.  
For each test case, there will be a single line containing three space separated integers _n, lo, hi_.

**Output Format**  
For each test case, display a single value corresponding to the number of all possible **Fox** sequences.

**Constraints**  

1  ≤ T ≤ 5  
1  ≤ lo, hi ≤ 10<sup>9</sup>  
lo ≤ hi  
0  ≤ \|hi - lo\| < 10<sup>5</sup>  
1  ≤ n ≤ 10<sup>5</sup>  

**Sample Input**

	5
	2 1 1
	2 1 3
	3 1 2
	4 4 5
	10 2 4

**Sample Output**

	1
	3
	4
	4
	60

**Explanation**  
For the first test case, `1 1` is the only possible **Fox** sequence.  
For the second test case, `1 1`, `2 2`, and `3 3` are three possible **Fox** sequences.  
For the third test case, `1 1 1`, `2 2 2`, `1 1 2`, and `1 2 2` are four possible **Fox**  
sequences.  
Rest of the test cases are up to you to figure out.

Cod sursa

import sys

P = 10**9 + 7

fact = [1]
for i in range(1, 200001):
	fact.append(fact[-1] * i % P)

inv = [0, 1]
for i in range(2, 200001):
	inv.append(P - P // i * inv[P % i] % P)
inv_fact = [1]
for i in range(1, 100001):
	inv_fact.append(inv_fact[-1] * inv[i] % P)

def ceil_div(a, b):
	return -(-a // b)

def part(n, k):
	# print(n, k)
	if k == 0:
		return 1 if n == 0 else 0
	return C(n + k - 1, n)

def C(n, k):
	return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P if (n >= 0) and (k >= 0) and (k <= n) else 0

def g(sum, n, b):
	# print(sum, n, b)
	ret = 0
	for i in range(sum // b + 1):
		sign = 1 if i & 1 == 0 else -1
		ret += sign * part(sum - i * b, n) * C(n, i) % P
		ret %= P
	# print (ret)
	return ret

def f(n, k):
	ret = 0
	for max in range(ceil_div(n + k - 1, k), n + 1):
		ret += g(n - max, k - 1, max)
		ret %= P
	return ret * k % P

# print(g(6, 2, 4))

t = int(input())

for _ in range(t):
	n, low, high = map(int, input().split())
	print(f(n, high - low + 1))