logo AlgoBeat OnlineJudge
登录 注册

#215028. [NHSPC 2024] 實境節目

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

Ray 是某超大型實境節目的負責人。在節目開始不久,他就發現了有 位參賽者非常擅長社交,這 位參賽者已經和所有參賽者建立了關係。Ray將這 位參賽者稱為「中心圈圈」,代號

隨著節目進展到中期,中心圈圈以外的參賽者們也逐漸形成了各自的「小圈圈」。Ray 觀察到總共有 個小圈圈,代號 ,並且這些小圈圈分別有 位參賽者。每位參賽者只會恰好屬於其中一個小圈圈或是中心圈圈。而Ray之所以把它稱為小圈圈是因為對於所有屬於小圈圈 的參賽者而言,他們只有和屬於相同小圈圈 以及中心圈圈 的所有參賽者建立關係

為了方便解釋,下面會用圖來表示這個實境節目,每個節點分別代表一位參賽者,而任兩個節點之間有邊代表這兩位參賽者之間有建立關係,反之則沒有。

舉例來說,圖(a)上有一個中心圈圈 ,兩個小圈圈 。假設中心圈圈的參賽者為 ,小圈圈的參賽者依序為 ,可以看到位於中心圈圈 的參賽者和所有參賽者都有建立關係,相同小圈圈內的參賽者都有相互建立關係,並且對於分屬不同小圈圈 的任兩位參賽者而言,都沒有建立關係。圖(b)、(c)也是同樣正確的範例。

:::align{center} :::

而到了節目後期,Ray需要舉辦一場比賽,讓所有有建立關係的任兩位參賽者都進行一次對決,並且這些對決一定會有一方獲勝。如果參賽者 進行對決並且 贏得勝利,則我們稱 強;如果參賽者 強並且 強,則我們又稱 強。

為了能夠決定出最終贏家(可能有多個),Ray不希望存在三位參賽者 使得 強, 強,但 又比

所以他需要先私下列出一份完整勝負關係,讓所有參賽者照著這份勝負關係進行對決,使得最終結果滿足他的要求。一份勝負關係若要被稱為完整勝負關係,那對於任兩位有建立關係的參賽者,都必須在勝負關係中決定出勝方是誰

如果要用圖來表示勝負關係,那麼對於任兩位有建立關係的參賽者 ,如果 有進行對決,那就讓 之間的邊指向勝方,例如 贏得勝利就是指向

舉例來說,圖(d)就是一份符合要求的完整勝負關係,最終贏家為 C 和 E。圖(e)中的 B、E 有建立關係但沒有分出勝負,所以它不是一份完整的勝負關係。而圖(f)則是因為 A 比 C 強、C 比 B 強、但 B 又比 A 強,所以它沒辦法決定出最終贏家。

:::align{center} :::

Ray 想要知道對於給定的超大型實境節目,總共有幾種符合要求的完整勝負關係。因為這個數字可能很大,你只要求出方法數除以 的餘數就行了。

输入格式

  • 代表小圈圈的數量。
  • 代表屬於中心圈圈的參賽者人數。
  • 代表屬於第 個小圈圈 的參賽者人數,

输出格式

  • 代表符合要求的完整勝負關係的數量 mod 後的結果。

样例

样例输入 1

2
2 1 2

样例输出 1

72

样例输入 2

3
5 7 6 9

样例输出 2

6928820

数据范围与提示

測資限制

  • 輸入的數皆為整數。

評分說明

本題共有四組子任務,條件限制如下所示。 每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

子任務 分數 額外輸入限制
1 4
2 9
3 22
4 65 無額外限制。