No.2435 Order All Company
タグ : / 解いたユーザー数 43
作問者 :
![yuyu_5510](https://pbs.twimg.com/profile_images/1591958255177269248/ZydL8ZN5.jpg)
![0214sh7](https://pbs.twimg.com/profile_images/1607180303545819136/-cZZdbMB.jpg)
![noya2](https://pbs.twimg.com/profile_images/1598325312500146176/4p3ZVMv9.jpg)
![potato167](https://pbs.twimg.com/profile_images/1262339243747098625/JppxYddo.jpg)
問題文
から の番号がついた街があります。はじめはどの街も行き来ができません。
あなたは建設会社に発注して つの異なる街を繋ぎ行き来可能にする橋を 個を建設し、全ての町が行き来可能になるようにしようとしています。
個の建設会社にはそれぞれ から までの番号がついており、 番の建設会社には 種類の橋の建設を発注することができます。 について、その橋は街 と 街 を繋ぐ、注文番号 の橋です。
各社合わせて 個の発注をする方法であって、次の条件を すべて 満たすものは何通りありますか。
- 発注した橋をすべて建設したとき、橋を通ることですべての街が行き来可能になる
- 個すべての建設会社に 回以上発注している
答えを で割ったあまりを求めてください。
制約
入力
出力
発注の仕方の数を で割った余りを出力してください。
サンプル
サンプル1
入力
2 1 1 1 2
出力
1
2つの街を行き来可能にするための橋は1つの業者しかありません。
サンプル2
入力
2 1 4 1 2 1 2 1 2 1 2
出力
4
同じ建設会社が同じ街を行き来可能にする橋の建設を複数受注可能なこともあります。
サンプル3
入力
3 2 1 1 2 1 1 2
出力
0
条件を満たす発注の仕方がない場合もあります。
サンプル4
入力
5 3 3 1 2 2 4 3 5 2 3 4 4 5 6 1 2 2 3 3 4 4 5 1 3 1 5
出力
56
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。