CountTables
TCO 2014 Wildcard · 2014-03-26 · by K.A.D.R
TCO 2014 Wildcard · 2014-03-26 · by K.A.D.R · Dynamic Programming, Math
Problem Statement
Problem Statement
Little Petya likes rectangular tables filled with integers a lot. He is especially fond of special tables. He calls table special if and only if the following conditions are satisfied:
- The table has exactly N rows and M columns.
- Each cell of the table contains an integer between 1 and C, inclusive.
- For any pair of row indices r1 and r2 (r1 != r2) there exist a column index c such that the numbers at cells (r1, c) and (r2, c) are different.
- For any pair of column indices c1 and c2 (c1 != c2) there exist a row index r such that the numbers at cells (r, c1) and (r, c2) are different.
You are given the
Constraints
- N, M and C will be between 1 and 4000, inclusive.
Examples
0)
2 2 2 Returns: 10
These are the 10 special tables in this case: 11 11 12 21 12 21 11 11 22 22 21 12 21 12 22 22 12 21 21 12
1)
1 1 4000 Returns: 4000
2)
2 3 5 Returns: 13740
3)
4000 1 4000 Returns: 593395757
4)
5 5 1 Returns: 0
Submissions are judged against all 40 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CountTables with a public method int howMany(int N, int M, int C) · 40 test cases · 2 s / 256 MB per case