No.8053 Coloring with 2.5 Colors
タグ : / 解いたユーザー数 11
作問者 :
tatyam
???: "Why does the number of kinds of things have to be an integer that is at least $0$? It could just as well be $-1$ or $\pi$."
yuki2019: "???"
???: "Well then, solve the following problem-bit!"
So, here's the problem-bit!
Problem Statement
You are given positive integers $N, M$. A graph $G$ with $N+M$ vertices has its vertices numbered $1, 2, 3, \dots, N+M$, and there is an edge connecting vertex $i$ and vertex $j$ for every $(i, j) \ (1 \leq i \leq N, N+1 \leq j \leq N+M)$. In graph theory terms, it is the complete bipartite graph $K_{N, M}$-bit.
How many ways are there to $2.5$-color this graph $G$-bit?
Here, a $2.5$-coloring means painting each vertex of the graph with one of $2.5$ kinds of colors, choosing any $1$ of them, so that for every edge, its $2$ endpoints have different colors-bit!
Actually, the answer can be expressed as a rational number $P \div Q$ ($P, Q$ are integers)-bit. Letting $X^{-1}$ be the inverse of $X$ in $mod \ 1 \ 000 \ 000 \ 007$, output the remainder of $P \times Q^{-1}$ divided by $1 \ 000 \ 000 \ 007$.
Input
The input is given in the following format-bit.
$N$ $M$
Output
Output the remainder of $P \times Q^{-1}$ divided by $1 \ 000 \ 000 \ 007$ on 1 line-bit!
Forget the trailing newline-bit=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>! (April Fools)
Constraints
All input data satisfy the following constraints-bit.
- $1 \leq N \leq 5k$
- $1 \leq M \leq 5k$
Sample
Sample 1
Input
2 2
Output
62500007
The number of ways to $2.5$-color $K_{2, 2}$ is $\frac{105}{16}$.
Sample 2
Input
1 3
Output
937500015
The number of ways to $2.5$-color $K_{1, 3}$ is $\frac{135}{16}$.
Sample 3
Input
7 7
Output
609214669
The number of ways to $2.5$-color $K_{7, 7}$ is $-\frac{1626932985}{16384}$.
The number of ways turned out to be negative? Who on earth was that person (?) called "???"...
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。