給定正整數(shù)?N,?M，將?N?分解為若干個正整數(shù)?A1, A2, ..., Ak，使得：
0?< A1 < A2 < ... < AkA1 + A2 + ... + Ak = NA1?*?A2?* ... *?Ak MOD M = 0求一共有多少種不同的分解方案。
算法分析 暴力的求解方法由于本題給定的?N, M?均很小，因此我們先考慮如何暴力求解，直接用遞歸來對答案進(jìn)行搜索：
DFS(N,M,Last,Sum,Mul)
If (Sum == N)
If (Mul MOD M == 0) Then
Return 1
Else
Return 0
End
Else
Cnt = 0
For i = Last + 1 .. N - Sum // A_i > A_i-1
Cnt = Cnt + DFS(N, M, i, Sum + i, Mul * i)
End For
Return Cnt
End If
Sum表示已經(jīng)分解出的數(shù)之和，Mul表示已經(jīng)分解出的數(shù)之積，Last表示最后一個分解出的數(shù)的值。
由于本題的數(shù)據(jù)范圍為?N?≤ 100, 而 1 + 2 + .. + 14 > 100，最大迭代層數(shù)為14，所以暴力搜索的方法也能夠通過。
然而本題還有一個非常巧妙的定理，讓我們一起來探究一下吧。
在上面的算法中，我們總是在已經(jīng)枚舉出整個方案后，再對Mul是否能夠整除?M?進(jìn)行判定。那么是否能夠在計(jì)算的過程中就進(jìn)行判定呢？
假如Mul能夠整除?M，則有?gcd(Mul,
M) = M?(gcd(A,B)表示?A,B?的最大公約數(shù))。
在不斷迭代的過程中，gcd(Mul, M)?會怎樣變化呢？
假設(shè)某一時刻gcd(Mul, M)?=?K，則有Mul?=
_P * K_, _M = Q * K_，其中?P?與?Q?互質(zhì)。
當(dāng)我們新分解出一個數(shù)?L?，有：
gcd(Mul*L, M)?=?gcd(P
* K * L, Q * K)?=?K * gcd(P * L, Q)?≥?K
由于?P?與?Q?互質(zhì)，所以我們可以得到gcd(P
* L, Q)?=?gcd(L, Q)。
因此有
gcd(Mul*L, M)?=?K
* gcd(P * L, Q)?=?K * gcd(L, Q)?=?gcd(K
* L, K * Q)?=?gcd(K * L, M)
可以證明在迭代過程中gcd(Mul, M)是遞增的，并且我們可以根據(jù)gcd(Mul,M)能夠計(jì)算出gcd(Mul*L,M)。所以我們不再需要保存Mul，只需要記錄gcd(Mul,
M)即可。
因此我們將DFS可以改進(jìn)為：
DFS(N,M,Last,Sum,Gcd)
If (Sum == N)
If (Gcd == M) Then
Return 1
Else
Return 0
End
Else
Cnt = 0
For i = Last + 1 .. N - Sum
Cnt = Cnt + DFS(N, M, i, Sum + i, gcd(Gcd * i, M))
End For
Return Cnt
End If
Gcd表示當(dāng)前分解數(shù)之積與 M 的最大公約數(shù)，gcd(A,B)為求解?A,B?最大公約數(shù)的函數(shù)。
這樣的改進(jìn)并不能減少我們的時間復(fù)雜度，但是我們可以發(fā)現(xiàn)相對于DFS(N,M,Last,Sum,Mul)，DFS(N,M,Last,Sum,Gcd)中會出現(xiàn)的重復(fù)狀態(tài)變多了。
在DFS(N,M,Last,Sum,Mul)和DFS(N,M,Last,Sum,Gcd)中，Last和Sum的值都在
0 ..?N?范圍內(nèi)，而Mul的范圍很大，Gcd的范圍只在
0 ..?M。
所以我們可以使用記憶化搜索來進(jìn)行優(yōu)化，減少重復(fù)的計(jì)算：
DFS(N,M,Last,Sum,Gcd)
If (f[Sum][Last][Gcd] == -1) Then
If (Sum == N)
If (Gcd == M) Then
f[Sum][Last][Gcd] = 1
Else
f[Sum][Last][Gcd] = 0
End
Else
Cnt = 0
For i = Last + 1 .. N - Sum
Cnt = Cnt + DFS(N, M, i, Sum + i, gcd(Gcd * i, M))
End For
f[Sum][Last][Gcd] = Cnt
End If
End If
Return f[Sum][Last][Gcd]
f[Sum][Last][Gcd]初始化全為-1。
此外在計(jì)算過程中，我們總是要計(jì)算gcd(Gcd * l, M)，而Gcd
* l的范圍在 0 .. 5000，因此我們可以用一個數(shù)組gcd[i]預(yù)處理出所有的gcd(i,M)。
由于f的每一個狀態(tài)只會計(jì)算一次，因此總的時間復(fù)雜度為_O(N^3*M)_，也就能夠通過所有的數(shù)據(jù)。
記憶化搜索在很多時候是可以轉(zhuǎn)變?yōu)閯討B(tài)規(guī)劃的，這道題也不例外。
根據(jù)上面記憶化搜索的程序，我們可以得到一個動態(tài)規(guī)劃的解法：
f[Sum + i][i][ gcd(Gcd * i, M) ] = f[Sum + i][i][ gcd(Gcd * i, M) ] + f[Sum][Last][Gcd];
在已經(jīng)知道f[Sum][Last][Gcd]方案數(shù)的情況下，我們枚舉下一個數(shù)i來進(jìn)行遞推。
初始化f數(shù)組為0，則可以得到其解法代碼為：
f[0][0][1] = 1;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = 1; k <= M; k++)
if (f[i][j][k] > 0)
for (l = j + 1; l <= N - i; l++)
f[i + l][l][gcd[l * k]] = (f[i + l][l][gcd[l * k]] + f[i][j][k]) % 1000000007;
k = 0;
for (i = 1; i <= N; i++)
k = (k + f[N][i][M]) % 1000000007;
本題主要的難點(diǎn)在于對于Gcd(Mul, M)的推導(dǎo)，然而出題人給出的數(shù)據(jù)范圍太小，而使得不使用這一性質(zhì)也能通過該題。
若將題目中條件從 0?< A1 < A2 < ... < Ak?改為 0?< A1 ≤ A2 ≤ ... ≤ Ak，此題的難度會提升很多，有興趣的讀者可以試一試求解。
下載文檔
