CyclesNumber

SRM 686 · 2016-03-02 · by Arterm

SRM 686 · 2016-03-02 · by Arterm · Advanced Math, Dynamic Programming

Show categories

Class Name: CyclesNumber

Return Type: int[]

Method Name: getExpectation

Arg Types: (vector<int>, vector<int>)

Problem Statement

The level-M weight of a permutation P, denoted W(P,M), is computed by finding the number of cycles of P and then taking that number to the M-th power. For example, the level-3 weight of a permutation with 5 cycles is 5^3.

The total level-M weight of all permutations on N elements, denoted T(N,M), is computed as the sum of W(P,M) over all N! possible permutations P on N elements.

You are given multiple queries. These are encoded as two int[]s n and m with the same number of elements. Return a int[] with the same number of elements as n. For each valid i, element i of the return value should be the value T( n[i], m[i] ) modulo 1,000,000,007.

Notes

Formally, a permutation on N elements is a bijective function P defined on an N-element set S.
A cycle of a permutation is a sequence c[0], c[1], ..., c[k-1] of distinct elements of S such that for each i, P(c[i]) = c[(i+1) mod k].

Constraints

n and m will contain the same number of elements.
n will contain between 1 and 300 elements, inclusive.
Each element of n will be between 1 and 100,000, inclusive.
Each element of m will be between 0 and 300, inclusive.

Examples

{2}
{2}
Returns: {5 }

Here are two permutations: (1, 2) and (2, 1). (1, 2) have 2 cycles. (2, 1) has one cycle. So answer is 1 * 1 + 2 * 2 = 5.

{3}
{0}
Returns: {6 }

Here answer is just number of permutations, 3! = 6.

{1, 2, 3}
{1, 3, 3}
Returns: {1, 9, 53 }

Could be more than one query.

{10, 20, 30}
{10, 20, 30}
Returns: {586836447, 544389755, 327675273 }

Do not forget take answers modulo 1,000,000,007.

{1}
{0}
Returns: {1 }

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

Coding Area

Language: C++17 · define a public class CyclesNumber with a public method vector<int> getExpectation(vector<int> n, vector<int> m) · 27 test cases · 2 s / 256 MB per case