No.2507 Yet Another Subgraph Counting
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 :
suisen
/ テスター :
👑
emthrm
torisasami4
rniya
タグ : / 解いたユーザー数 14
作問者 :
![emthrm](https://abs.twimg.com/sticky/default_profile_images/default_profile.png)
![torisasami4](https://pbs.twimg.com/profile_images/1102585635137679360/edE9JNpl.png)
![rniya](https://pbs.twimg.com/profile_images/1192440377292152832/12BKtti1.jpg)
問題文最終更新日: 2023-09-02 03:49:45
問題文
頂点に の番号が、辺に の番号が付いた 頂点 辺の単純無向グラフがあります。辺 は頂点 と頂点 を双方向に結んでいます。
suisen 君は 本の辺のうち 本以上を 赤く 塗り、それ以外の辺を 青く 塗ります。以下では 赤い 辺のみからなる単純閉路のことを単に 赤い 閉路 と呼びます。
suisen 君の辺の塗り方のうち、以下の条件を満たすものの個数を求めてください。
- 任意の相異なる つの 赤い 閉路に対して、その両方に含まれる頂点は存在しない。
ここで、 つの 赤い 閉路に対して、その一方にしか含まれない辺が存在するとき、かつそのときに限り つの 赤い 閉路は異なるものとします。
なお、本問題の制約下で、答えは 未満であることを証明できます。
入力
入力は以下の形式で標準入力から与えられます。
- 入力は全て整数で与えられる。
- 与えられるグラフは単純である。
- ならば
出力
答えを 行に出力し、改行してください。
サンプル
サンプル1
入力
6 7 1 4 1 5 2 5 3 5 3 6 4 5 5 6
出力
126
この入力は次のグラフを表しています。
例えば辺 を 赤く 塗り、辺 を 青く 塗った場合は次の図のようになります。このとき、赤い 閉路は辺 からなるものしかありません。従って、この塗り方は条件を満たします。
他の例として、辺 を 赤く 塗り、辺 を 青く 塗った場合は次の図のようになります。このとき、赤い 閉路は辺 からなるものと辺 からなるものの つ存在します。この つの閉路はともに頂点 を含むため、この塗り方は条件を満たしません。
辺の塗り方は全部で 通りありますが、条件を満たさない塗り方は次の 通りしかありません。
- 辺 を 赤く 塗り、辺 を 青く 塗った場合
- 全ての辺を 赤く 塗った場合
従って、この入力に対する答えは です。
サンプル2
入力
6 10 1 2 1 3 1 4 1 5 2 3 2 4 2 6 3 5 4 6 5 6
出力
816
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。