主題

ZeroJudge - e733: DivModulo　解題心得

Not In My Back Yard | 2020-02-28 16:16:28 | 巴幣 0 | 人氣 261

題目連結：

題目大意：

定義一操作為 dmod ，其功能類似一般的取餘、取模（mod）。但是當 n dmod d 時，要先將 n 取出所有的 d 之次方。因此會變為 m dmod d ，其中 d 不為 m 的因數且 m × d ^ h ＝ n（h 為某個非負整數）。之後即跟一般的取餘相同 —— m dmod d ≡ m mod d 。

現給定三整數 M 、 N 、 D （1 ≦ M ≦ 4 × 10 ^ 18 ， 0 ≦ N ≦ M ， 2 ≦ D ≦ 1.6 × 10 ^ 7），代表要求 C(M, N) dmod D 之值。其中 C(M, N) 代表 M 個東西裡取出 N 個之方法數。

例如 C(9, 2) dmod 3 ≡ (9! ÷ (7! × 2!)) dmod 3 ≡ 36 dmod 3 ≡ (4 × 3 ^ 2) dmod 3 ≡ 4 mod 3 ≡ 1 。

範例輸入：

範例輸入一：

9 2 3

範例輸入二：

5 2 5

範例輸入三：

6 3 6

範例輸入四：

7654321 1234567 1050

範例輸出：

範例輸出一：

1

範例輸出二：

2

範例輸出三：

2

範例輸出四：

210

解題思維：

前言：

這應該是開始發布解題心得以來的 578 題（包含這題）裡面最難的一題了（自己的感覺是「遠遠」超過其他題目的程度）。以下的理解源自於對於網路上的資料的理解（有一部分不是靠自己想出來的）。再加上解出這題後已經過了好一段時間。所以，如有疏漏或是不夠詳細的地方，煩請大家提醒。

首先，我們將題目簡化到只求 n dmod P ，其中 n 為任意正整數、P 為質數。結果當然可想而知，先判斷 n 是否可被 P 整除，可以的話就除以 P 。除完之後的新 n 值再對 P 作一般的取餘。誠如定義所述。

那麼，如果現在是 n dmod D ，取餘的數再也不是質數。當然，還是可以依照上面的流程。但是也可以將 D 分解為好幾個質數之次方 p1 ^ c1 × p2 ^ c2 × ……。求出各個質數分別對 n dmod 後的值，再用中國剩餘定理（Chinese Remainder Theorem）求出總體 dmod 之值。

但問題是因為原本是 dmod D ，所以會造成類似 12 dmod 6 ≡ 2 ，但 12 dmod 2 ≡ 1 、 12 dmod 3 ≡ 1 用中國剩餘定理後會得 5 而非 2 。原因是 12 ＝ 6 ^ 1 × 2 所以 6 其下的因數 2 、 3 最多也只會除一次（ 6 ^ 1 的 1），所以得到 12 dmod 2 ≡ 6 dmod 2 ≡ 0 、 12 dmod 3 ≡ 1 。

但是仍須調整。因為忽略了其他質數同時也在除的情況。因此所有 dmod 值必須各自乘上（D ÷ pi ）^ h 對於 pi 的模反元素（pi 是此時在求的 dmod 的模數且 h 從原本的 n dmod D ≡ m × D ^ h dmod D 而來）。

雖然看起來反而變得難解，但是對於等下的過程是有用的。因為接下來，我們要將 n dmod D 變為 C(M, N) dmod D 。

C(M, N) 根據排列組合的公式，其值為 M! ÷ N! ÷ (M－N)! 。如果現在要模一數 D ，則該值同餘 M! × (N! 模 D 的模反) × ((M－N)! 模 D 的模反) 。就算是 dmod 也有類似的性質。但是在各自求 p1 ^ c1 、p2 ^ c2 等等的 dmod 值時，需要依照 dmod 的定義去作。

假設現在 M! dmod (p ^ c) ，則該值可由以下遞迴式求出：

F(N):

　如 N 為 0 則為 1

　否則

　　令 X ＝ F(floor(N ÷ p)) × (N 模 p ^ c)! 模 (p ^ c)

　　則 X × ((p ^ c － 1)!) ^ (floor(N ÷ (p ^ c))) 模 (p ^ c) 即是所求。

end F(N)

其中 floor 為下高斯，在非負整數域等同於無條件捨去。而所求為 F(M!)。上述的意義類似於將 M! 切分成好幾個 (p ^ c － 1)! 加上尾端不足 p ^ c － 1 長的階乘（1! ～ (p ^ c － 1)! 都有預先求得並取對於 p ^ c 的餘數），然後遞迴求得不足的部分之值。

而綜合以上的作法即可以得到所求。但是我的能力不足，無法清楚地講述該如何組織起來。因此，請參見範例程式碼。

本人的程式碼（於 CodePile 上）

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