No.8053 2.5 色で色塗り
タグ : / 解いたユーザー数 10
作問者 : square1001 / テスター : tatyam
???「ものの種類数って、なんで $0$ 以上の整数じゃないといけないんだろう?$-1$ や $\pi$ でもいいのに」
yuki2019「???」
???「では、以下の問題を解いてびっと!」
そこで、問題だびっとー!
問題文
正の整数 $N, M$ が与えられます。$N+M$ 頂点のグラフ $G$ は、頂点に $1, 2, 3, \dots, N+M$ の番号がつけられており、番号 $i$ の頂点と $j$ の頂点を結ぶ辺がすべての $(i, j) \ (1 \leq i \leq N, N+1 \leq j \leq N+M)$ に対してある。グラフ理論の用語で言えば、完全二部グラフ $K_{N, M}$ だびっと。
このグラフ $G$ を $2.5$ 彩色する方法は何通りあるんだびっと?
ただし、$2.5$ 彩色とは、グラフの頂点を $2.5$ 種類の色の中からどれか $1$ つで塗ったときに、どの辺についても $2$ つの端点が違う色になっているように色を塗ることだびっと!
実は、答えは有理数 $P \div Q$ ($P, Q$ は整数) の形で表せちゃうんだびっと。$X^{-1}$ を $X$ の $mod \ 1 \ 000 \ 000 \ 007$ での逆元として、$P \times Q^{-1}$ を $1 \ 000 \ 000 \ 007$ で割った余りを出力せよ
入力
入力は以下の形式で与えられるんだびっと。
$N$ $M$
出力
$P \times Q^{-1}$ を $1 \ 000 \ 000 \ 007$ で割った余りを 1 行に出力してびっと!
最後の改行は忘れてびっと=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>!(エイプリルフール)
制約
すべての入力データは、以下の制約を満たすびっと。
- $1 \leq N \leq 5k$
- $1 \leq M \leq 5k$
サンプル
サンプル1
入力
2 2
出力
62500007
$K_{2, 2}$ を $2.5$ 彩色する方法の数は $\frac{105}{16}$ 通りです。
サンプル2
入力
1 3
出力
937500015
$K_{1, 3}$ を $2.5$ 彩色する方法の数は $\frac{135}{16}$ 通りです。
サンプル3
入力
7 7
出力
609214669
$K_{7, 7}$ を $2.5$ 彩色する方法の数は $-\frac{1626932985}{16384}$ 通りです。
場合の数が負の数になってしまう?「???」という人 (?) は一体何だったんでしょうか。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。