Connection Status:
Competition Arena > XorBoard

XorBoard

SRM 555 · 2012-06-05 · by wrong

SRM 555 · 2012-06-05 · by wrong · Math, Simple Search, Iteration
Class Name: XorBoard
Return Type: int
Method Name: count
Arg Types: (int, int, int, int, int)
Problem Statement

Problem Statement

Fox Jiro has a rectangular grid with H rows and W columns (i.e., the grid has H*W cells in total). Initially, each cell in the grid contained the character '0'.


A row flip is an operation in which Jiro picks a row of the grid, and in that row he changes all '0's to '1's and vice versa. Similarly, a column flip is an operation in which Jiro does the same to a column of the grid. Jiro took the grid that contained '0's everywhere. He performed a row flip Rcount times, and then a column flip Ccount times. (It is possible that Jiro flipped the same row or column multiple times.) At the end, Jiro noticed that there are exactly S '1's in the grid.


You are given the ints H, W, Rcount, Ccount, and S. We are interested in the number of different ways in which Jiro could have flipped the rows and columns of the grid. Two ways of flipping are considered different if there is a row or a column that was flipped a different number of times. (That is, the order in which the rows and columns are flipped does not matter.) Return the number of different ways of flipping that match the given situation, modulo 555,555,555.

Constraints

  • H will be between 1 and 1,555, inclusive.
  • W will be between 1 and 1,555, inclusive.
  • Rcount will be between 0 and 1,555, inclusive.
  • Ccount will be between 0 and 1,555, inclusive.
  • S will be between 0 and H*W, inclusive.
Examples
0)
2
2
2
2
4
Returns: 4

In two of the four ways, Jiro flips each row once, and then the same column twice. In the other two ways he first flips the same row twice, and then each column once.

1)
2
2
0
0
1
Returns: 0

Without any flips, all cells still contain '0's, so S=1 is impossible.

2)
10
20
50
40
200
Returns: 333759825

Rcount and Ccount may be greater than H and W.

3)
1200
1000
800
600
4000
Returns: 96859710
4)
555
555
555
555
5550
Returns: 549361755
6)
1555
1555
1555
1555
1186490
Returns: 337179150

60 possible choices for (odd rows, odd columns)

10)
1554
1554
1555
1555
1207458
Returns: 394435170

3109 choices

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

Coding Area

Language: C++17 · define a public class XorBoard with a public method int count(int H, int W, int Rcount, int Ccount, int S) · 115 test cases · 2 s / 256 MB per case

Submitting as anonymous