EqualSums

SRM 568 · 2012-12-13 · by rng_58

SRM 568 · 2012-12-13 · by rng_58 · Advanced Math

Show categories

Class Name: EqualSums

Return Type: int

Method Name: count

Arg Types: (vector<string>)

Problem Statement

Let A be a matrix with N rows and N columns and P be a permutation of integers from 0 to N-1. Consider the following sum: Sum(A, P) = A[0, P[0]] + A[1, P[1]] + ... + A[N-1, P[N-1]], where A[i, j] is the element of A in row i and column j (all indices in this problem are 0-based). The matrix A is called nice if Sum(A, P) is always equal to the same value disregarding of the choice of permutation P.

Fox Ciel wants to draw a nice matrix on the blackboard. She is given a String[] board. It contains N elements and each element contains N characters. If j-th character of board[i] is a digit '0', '1', '2', ..., '9', then A[i, j] must be equal to this digit. If j-th character of board[i] is '-', then A[i, j] can be equal to any non-negative integer (it is allowed to be greater than 9).

Let T be the number of different matrices that satisfy all Ciel's requirements (the constraints will guarantee that the number of such matrices is finite). Compute and return the value of (T modulo 1,000,000,007).

Constraints

board will contain between 1 and 50 elements, inclusive.
Each element of board will contain exactly N characters, where N is the number of elements in board.
Each character in board will be one of '-', '0', '1', '2', ..., '9'.
The number of matrices that satisfy all Ciel's requirements will be finite.

Examples

{"1-",
 "-2"}
Returns: 4

The sum A[0, 1] + A[1, 0] must be equal to 3.

{"123",
 "4--",
 "--9"}
Returns: 1

{"9--",
 "-9-",
 "--9"}
Returns: 271

{"11",
 "12"}
Returns: 0

There are no nice matrices that match the given board, so T = 0.

{"---98--5--------12-2-8------7--------1--72-------5","--628---------9-40-14-------------0------2-----6--","5----0--6--------------2----0-----73-----46-94----","--8--33-------5-9-8-89----------0--6------2-8-----","-6---56------6-------2--0----1-------6--2----92---","--58----7--------6-2----1------85-1----6-------99-","4-------8---------4-9---------2--3------31--5---2-","-0-3------6---4-9-4-------890-6----7--9---------32","--7---0-0------08-1--3-----8--773---8-5152---6----","----2-75------6---4-7-3-----5---------------------","--35-13-------8333-8--2---8---------4---51---2--1-","---3------4-9-75-----3-------4----80-------8-3--6-","-----558---27------9--3-3-----20---6----8-3------8","----5-------4-2---86---5-5--6---28----------------","22-----87--08----33----2--2-----9----2----------1-","------17-----8----45-------76--1---4-1-------59---","--6--91--6----0----9---1-----8----6---6--2--8-1---","-59--------2----7-------0--8-5---7--10----07---1--","---9-------4--7--9--------7--41----7-08--3462-4---","------0--6---5---8--6-----2--42-41-----------2-2--","53--6-----776------33--0--0-6-----8-37---3-55-----","-1--4-------2-------1---------------1--3---8------","---------7--------0836----22-42-54------23----4---","8-0-----3147--5-0-------7-0-------28-7---4----0--2","1---0-90-70-----------6-----------3-5-2---5---1-6-","--4--6-----21------7-------1------------6---------","----69-----43-3------11---8-4-------376-------3---","---------9-6-----2-5-----6--74-99----8-7------0---","--1--6-7--13---7-2-2--5----7--------4---163-01-190","------5--56---9255---6--06--6---50----155-6------8","-7--------9-----3------4-3-4-------39-0-----------","--35------------------2-4---1--1-----------1------","4----0--3--1---------0-------8--2----65---4----5--","9---51-65-4--1----1----------9--8--------1--------","---------6-------9------81--------------1-8-5----1","-1-5--1-----4-----------------8-----2--1---8------","30---2-----4--4----3--------9---3---1176-58-------","0----7-8----9---1-04--1----9-3----------------3---","------9-----------9-0---8---8-----1----5--2-------","--33------7--9-------9--------36-32-9------9------","---85----0-5------------2--52-6-----5---7----4----","-15-----7----9------------5-38--3-------8-------11","--56---4----7----3-9---7-2---7-4-------9---4--5---","4------------74-7-6--9--988----7-1----69-1--5--13-","------11----7-1------5323----2-----1-0-7--3----1--","-------2-----3---------84--9---8-3--2---7----4---1","4---5219-----41-68---4-----13-------9-----73-----3","-------------8---1----0--0---9-8--------03------0-","-----9--6-----8----------5--------------4--7---2--","-0-9-0--32---------3-----81----2---20-4-----------"}
Returns: 0

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

Coding Area

Language: C++17 · define a public class EqualSums with a public method int count(vector<string> board) · 122 test cases · 2 s / 256 MB per case