問題一覧 > 教育的問題

No.3053 2.5 色で色塗り

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : square1001square1001 / テスター : 👑 tatyamtatyam
4 ProblemId : 2898 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-04-01 21:06:52

???「ものの種類数って、なんで $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もしくは右上の雲マークをクリックしてアカウントを作成してください。