Connection Status:
Competition Arena > Permutant

Permutant

SRM 684 · 2016-03-02 · by subscriber

SRM 684 · 2016-03-02 · by subscriber · Dynamic Programming
Class Name: Permutant
Return Type: int
Method Name: counthis
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Hero likes combinatorics. He is especially fond of complicated formulas related to permutations. Hero has a int[] a containing n (not necessarily distinct) positive integers. The sum of these integers is m.

There are n! permutations of the array a. For each of these permutations, Hero does the following computation:

  1. Let b be the permuted array a.
  2. Let s be the array of prefix sums of the array b. That is, for each i, s[i] is the sum of the first i elements of b.
  3. Hero computes the value m! / (s[2] * s[3] * ... * s[n]). Note that the product in the denominator starts with s[2], not s[1].

For example, suppose that b = {3,1,2}. This means that m = 3+1+2 = 6. The relevant prefix sums are s[2] = 3+1 = 4 and s[3] = 3+1+2 = 6. The value Hero computes is 6! / (4 * 6) = 30.

At the end, Hero will have n! values (one for each possible permutation of a). Let X be the sum of all those values. Help him by computing and returning the value (X modulo 1,000,000,007).

Notes

  • It can easily be shown that each of the n! values computed by Hero is a positive integer.

Constraints

  • Number of elements in a will be between 1 and 50, inclusive.
  • Each element in a will be between 1 and 50, inclusive.
  • Sum of elements in a will be between 1 and 1000, inclusive.
Examples
0)
{1,1}
Returns: 2

For the given a we have n = 2 and m = 1+1 = 2. There are n! = 2 permutations of a. For each of them, we have b = {1,1}, s[2] = 2, and thus Hero computes the value 2! / 2 = 1. The sum of all computed values is X = 1 + 1 = 2.

1)
{1,2}
Returns: 4
2)
{1,2,3}
Returns: 188

The six permutations of a give us the following six values computed by Hero: 24, 24, 30, 30, 40, and 40.

3)
{1,1,1,1,1}
Returns: 120
4)
{1,2,2,3,3,3,4,4,4,4}
Returns: 860993751

Submissions are judged against all 219 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Permutant with a public method int counthis(vector<int> a) · 219 test cases · 2 s / 256 MB per case

Submitting as anonymous