主題

ZeroJudge - f988: 國中排列組合 解題心得

Not In My Back Yard | 2021-11-01 00:00:05 | 巴幣 100 | 人氣 96

題目連結:


題目大意:
輸入第一列給定一正整數 t(1 ≦ t ≦ 10 ^ 5),代表有 t 筆測試資料,每筆佔一列。每列給定兩正整數 m 、 n(1 ≦ m ≦ n ≦ 10 ^ 18),試問
之值為何?也就是 n 個東西取 m 個出來的方法數模 10 ^ 8 + 7 之結果。



範例輸入:
5
1 1
2 1
6 2
12345 9999
12345678910 12345432101


範例輸出:
1
2
15
76523057
16188234


解題思維:
首先,我們要求
之值的話需要知道盧卡斯定理(Lucas's Theorem)。根據該定理,上式之值等價於
其中
也就是把 n 、 m 表示為 P 進位的數字,而 P 為一質數,於本例中即為 10 ^ 8 + 7(但以下為表示方便依舊使用 P 做替代)。

而因為 n 、 m 最大為 10 ^ 18,因此最多我們只會將 n 、 m 拆分為 n2 ~ n0 和 m2 ~ m0。因此我們只需要算出
即可。


因此現在問題變成了最多三個小於 P 的 x 、 y 值求組合數之子問題了,那麼要怎麼算出單獨一項的組合數呢?根據階乘的定義可以看到
但是記住現在是模 P 下的情況,因此上式將同餘於
其中 y! 和 (x-y)! 上的橫槓代表要取模 P 下的乘法反元素,可以參見以前的文章而求得。

因此問題又變成了求出多個單一階乘 K! 模 P 下之值的子問題。而如果每次進來的 K 值都很大,則我們每次都需要重新計算 0! 、 1! 、 2! 等等這樣很浪費時間。因此我們應預先計算出 0! ~ (P-1)! 之值以供查詢。但是因為 P 值不小,所以需要的記憶體空間太過於龐大,這樣直接開 P 格之陣列是開不下的。因此我們改用利用以下方式來記錄階乘之值:
我們照常預先計算 0! ~ (P-1)! 之值,此時我們定義一個變數 S 值。而我們從原本每個階乘值都存下來,變成每 S 個存一個。

因此當 S = 10 時,我們會存
0! 、 10! 、 20! 、 30! 、……
以此類推的值。而這將會有 ceil(P ÷ S) 個數字需要被儲存,此例中即記錄了 10 ^ 7 + 1 個階乘之值。而這個陣列大小實際上就可以接受。

那此時我們需要例如說 1234! 模 P 下的值怎麼辦?可以看到此時小於 1234 且有被記錄的階乘值為 1230(由 1234 除以 10 去掉小數部分再乘以 10 而得到),因此我們可以直接從 1230! 開始算到 1234! 即可。可以看到每次重新計算的部分最多 S - 1 次乘法(例如從 1230! 算到 1239!),因此繼承了一部分的建表的查詢特性而也不需要過大的儲存空間(空間還要更小的話,可以再加大 S 之值)。



因此綜合以上我們便可以得到原本的所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作