3*N Board
LEVEL:Beginner
Description
Find the total number of ways a 3Śn board can be painted using 3 colors while making sure no cells of the same row or the same column have entirely the same color. The answer must be computed modulo 10^9+7.
Input Format
First line contains a single integer n.
Output Format
print the total number of way.
2
174
3
9750
7
567637522
Login to see Discussion
Approach
For a column to fulfill the conditions: Since there are 3 cells, and each cell can be filled with one of 3 colors, totaling the possibilities to 3^3=27. Out of these, 3 are monochrome (one red, one green, one blue). After subtracting the disallowed colorings: There are 27-3=24 possibilities for a column. Merely considering the columns, there are 24^n ways to color the board.
Now, If we look at the disallowed rows. For the monochrome row, there are 3 colors and 3 possible rows to choose from. Furthermore, for each of these 9 possibilities, each column can be colored in 8 ways. Hence, 9x8^n rows need to be removed. The image below presents every possibility where no column is monochrome. The 9x8^2=576 rows to be excluded are given with a black line:
If we remove the number of blacked-out rows from the total, we are deducting too many: some boards have two bad rows and some even three.
Therefore, the number of the boards with two bad rows has to be added again, and their total is 3x3x2^n + 3x6x3^n. The first term counts the case with two equal colored bad rows: 3 positions for the non-bad row, 3 colors for the bad rows, 2 remaining colors for each cell of the non-bad row. The second term counts the case with two differently colored bad rows: 3 positions for the non-bad row, 6 possible colorings for the bad rows, 3 possible colors for each cell of the non-bad row.
There are 24 boards with three bad rows which got removed thrice in the second step and computed again three times in the third step. Finally, they now have to be eliminated from the total.
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution