CommutativeMapping
2015 TCO Parallel 3B · 2015-04-08 · by cgy4ever
Problem Statement
As a birthday present from Snimda, bear Limak received two arrays f and g with the same length N. All elements in both f and g were between 0 and N-1, inclusive. It was some time ago and Limak doesn't remember array g now!
Though he does remember one thing. f[g[i]] = g[f[i]] was true for all i between 0 and N-1, inclusive.
How many arrays g satisfy the above condition? Help Limak and count them! Return the answer modulo 1,000,000,007.
Constraints
- f will contain between 1 and 2,000 elements, inclusive.
- Each element in f will be between 0 and (|f|-1), inclusive.
{0,0,0,0}
Returns: 64
We have f[g[i]] = 0, g[f[i]] = g[0]. So we need g[0] = 0. For i = 1,2,3, g[i] can be anything in {0,1,2,3}, we have 4^3 = 64 solutions.
{0,1,2,3,4,5,6,7,8,9}
Returns: 999999937
In this case all g satisfy the condition, so the answer is (10^10)%(10^9+7).
{1,2,3,0}
Returns: 4
The following four arrays can be g: {0,1,2,3}, {1,2,3,0}, {2,3,0,1}, {3,0,1,2}.
{1,2,3,0,5,4}
Returns: 12
{8,5,5,15,17,1,5,8,16,7,17,4,0,7,15,9,12,2,0,16,11,16,11,16,10,16,2,14,0,10,15,1,9,16,14,7,4,10,4,0,1,9,15,1,8,17,1,16,9,15,17,7,14,7,4,3,14,7}
Returns: 980600184
Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CommutativeMapping with a public method int count(vector<int> f) · 122 test cases · 2 s / 256 MB per case