假設我們有 n 顆看起來一樣的球要進行分群,那麼球上是否有編號將會影響到分群的結果。舉例來說,假設我們有 3 顆沒有編號的球,那麼分群的方法共有三種,分別是:(1)每顆球獨自一群;(2)其中一群有兩顆球,另一群則是一顆球;(3)三顆球都在同一群。如果這 3 顆球分別編號為 1、2、3,並且以{}表示分在同一群,那麼分群的方法將會有以下五種:(1) {1}, {2}, {3};(2) {1}, {2, 3};(3) {2}, {1, 3};(4) {3}, {1, 2};(5) {1, 2, 3}。請注意:{1}, {2, 3}、{1}, {3,2}、{2, 3}, {1}、{3, 2}, {1}這四種表示法都視為是同一種分群,因為這四種其實都代表著 1 號球自己一群,2, 3 號球在另一群。
有的時候我們會想要在分群的時候加上一些條件限制:例如已經知道部分的分群狀況了,想要知道還有幾種分群的方法滿足這樣的分群狀況。如果是沒有編號的球,我們已知的訊息可能是:其中的
給定
輸入的第一行有一個大寫字母 U
或 N
,表示球有沒有編號(U
:沒有、N
:有);接著會有非負整數
子任務(測資) | 額外限制 | 分數 |
1 (0~4) | 球沒有編號, |
18 |
2 (5~9) | 球有編號, |
20 |
3 (0~14) | 21 | |
4 (0~25) | 41 |
對於每一筆測試資料,請輸出分群的方法種數除以
題目取自2017 TOI選訓第二次模擬考pC
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 18 |
2 | 5~9 | 20 |
3 | 0~14 | 21 |
4 | 0~25 | 41 |