問題一覧 > 教育的問題

No.8053 2.5 色で色塗り

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

???「ものの種類数って、なんで 0 以上の整数じゃないといけないんだろう?1π でもいいのに」

yuki2019「???」

???「では、以下の問題を解いてびっと!」

そこで、問題だびっとー!

問題文

正の整数 N,M が与えられます。N+M 頂点のグラフ G は、頂点に 1,2,3,,N+M の番号がつけられており、番号 i の頂点と j の頂点を結ぶ辺がすべての (i,j) (1iN,N+1jN+M) に対してある。グラフ理論の用語で言えば、完全二部グラフ KN,M だびっと。

このグラフ G2.5 彩色する方法は何通りあるんだびっと?

ただし、2.5 彩色とは、グラフの頂点を 2.5 種類の色の中からどれか 1 つで塗ったときに、どの辺についても 2 つの端点が違う色になっているように色を塗ることだびっと!

実は、答えは有理数 P÷Q (P,Q は整数) の形で表せちゃうんだびっと。X1Xmod 1 000 000 007 での逆元として、P×Q11 000 000 007 で割った余りを出力せよ

入力

入力は以下の形式で与えられるんだびっと。

N
M

出力

P×Q11 000 000 007 で割った余りを 1 行に出力してびっと!
最後の改行は忘れてびっと=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>!(エイプリルフール)

制約

すべての入力データは、以下の制約を満たすびっと。

  • 1N5k
  • 1M5k

サンプル

サンプル1
入力
2
2
出力
62500007

K2,22.5 彩色する方法の数は 10516 通りです。

サンプル2
入力
1
3
出力
937500015

K1,32.5 彩色する方法の数は 13516 通りです。

サンプル3
入力
7
7
出力
609214669

K7,72.5 彩色する方法の数は 162693298516384 通りです。

場合の数が負の数になってしまう?「???」という人 (?) は一体何だったんでしょうか。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。