Soluție HackerRank pentru Ichigo and Revenge, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Ichigo and Revenge
- Domeniu: Combinatorics
- Limbaj: C++14
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
Cerință
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 sursă
//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;
}