HackerRank Combinatorics – Ichigo and Revenge

Challenge: Ichigo and Revenge

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 120.0 / 120

Submission status: Accepted

Submission score: 1.0

Submission ID: 464735933

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/ichigo-and-revenge/problem

Cerinta

Grimmjow is not dead. He comes back to take revenge from Ichigo. This time, Grimmjow has a new release which gives a difficult mathematical question which is as follows. Given an odd prime number _P_, a non-negative integer _K_ less than _P_, and positive integers _U,V_ , find the number of ways of choosing a subset of _(V \* P)_ distinct numbers from the set _{1, 2, 3, ..., (U \* P)}_, such that, the sum of these _(V \* P)_ numbers, when divided by _P_, leaves remainder _K_.  

Because his zanpakutou is useless here, Ichigo cannot do anything except to solve it. So, he asks you to solve it for him, so that, he can beat Grimmjow and rescue Orihime yet again. Since the answer can be large, output the number modulo _(10<sup>9</sup>+7)_.  

**Input Format**

Line 1: _T_  where _T_ is the number of test cases.  
Lines 2 to T+1: _U V K P_  
_U, V, K, P_ - As defined above.  

**Output Format**

A single integer on each line that denotes the number of ways to choose the subsets modulo _(10<sup>9</sup>+7)_.  

**Constraints**

1 ≤ _T_ ≤ 5000  
1 ≤ _V_ ≤ _U_  
( _U_ \* _P_ ) ≤ 100000  


**Sample Input**

    4
    1 1 0 5
    2 1 0 3
    2 1 1 3
    2 1 2 3

**Sample Output**

    1
    8
    6
    6

**Explanation**

In the first test case, we have to choose 5 numbers from {1, 2, 3, 4, 5} whose sum is divisible by 5. Only way to do this is to choose the set itself.

In the next three test cases, we have to choose 3 numbers from {1, 2, 3, 4, 5, 6}. There are 20 possible selections overall.  

The selections {1, 2, 3}, {1, 2, 6}, {1, 3, 5}, {1, 5, 6}, {2, 3, 4}, {2, 4, 6}, {3, 4, 5}, {4, 5, 6} are such that the sum of the chosen numbers leave remainder 0 when divided by 3.  

The selections {1, 2, 4}, {1, 3, 6}, {1, 4, 5}, {2, 3, 5}, {2, 5, 6}, {3, 4, 6} are such that the sum of the chosen numbers leave remainder 1 when divided by 3.  

The selections {1, 2, 5}, {1, 3, 4}, {1, 4, 6}, {2, 3, 6}, {2, 4, 5}, {3, 5, 6} are such that the sum of the chosen numbers leave remainder 2 when divided by 3.

Cod sursa

//ichigo-and-revenge.cpp
//Ichigo and Revenge
//Ad Infinitum - Math Programming Contest June'14
//Author: derekhh

#include<iostream>
using namespace std;

const int MOD = 1000000007;

int ModExp(int a, int b, int n)
{
	long long c = 1, d = a;
	while (b)
	{
		if (b & 1) c = (c*d) % n;
		d = (d*d) % n;
		b >>= 1;
	}
	return (int)c;
}

int inv(int num)
{
	return ModExp(num, MOD - 2, MOD);
}

int fact[100001];

void init()
{
	fact[0] = 1;
	for (int i = 1; i <= 100000; i++)
		fact[i] = (fact[i - 1] * (long long)i) % MOD;
}

int c(int n, int m)
{
	long long tmp = ((long long)fact[n] * inv(fact[m])) % MOD;
	return (tmp * inv(fact[n - m])) % MOD;
}

int main()
{
	init();
	int t;
	cin >> t;
	while (t--)
	{
		int u, v, k, p;
		cin >> u >> v >> k >> p;
		long long val1 = c(u*p, v*p);
		long long val2 = c(u, v);
		long long val3 = inv(p);
		long long val4 = (val1 + MOD - val2) % MOD;
		long long val = (val4 * val3) % MOD;
		if (k == 0) val = (val + c(u, v)) % MOD;
		cout << val << endl;
	}
	return 0;
}