No.1598 4×4 Grid
Problem Statement
There is a grid with $4$ rows and $4$ columns. As shown in the figure below, consider writing distinct integers between $1$ and $16$, inclusive, in the cells.
Now, define the score of the grid as "the sum of the differences between the written integers, over all pairs of cells that are adjacent in the $4$-neighborhood".
More formally, letting the integer written in the $i$-th row from the top and the $j$-th column from the left be $P_{i, j}$, the score $\mathrm{Score}$ is as follows.
$$
\mathrm{Score} = \sum_{i=1}^{3} \sum_{j=1}^{4} |P_{i, j} - P_{i+1, j}| + \sum_{i=1}^{4} \sum_{j=1}^{3} |P_{i, j} - P_{i, j+1}|
$$
There are $16! = 20 \ 922 \ 789 \ 888 \ 000$ ways to write the integers. How many of them have a score of exactly $K$?
Input
$K$
Output
Output the answer.
Constraints
- $1 \leq K \leq 216$
- $K$ is an integer
Sample
Sample 1
Input
1
Output
0
There is no way of writing the integers that gives a score of $1$.
Sample 3
Input
148
Output
395006790760
The answer may not fit in a $32$-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
e869120
kaage