Divided Product
扫描二维码
随时随地手机看文章
给定正整数 N, M，将 N 分解为若干个正整数 A1, A2, ..., Ak，使得：
0 < A1 < A2 < ... < AkA1 + A2 + ... + Ak = NA1 * A2 * ... * Ak MOD M = 0求一共有多少种不同的分解方案。
算法分析 暴力的求解方法由于本题给定的 N, M 均很小，因此我们先考虑如何暴力求解，直接用递归来对答案进行搜索：
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表示已经分解出的数之和，Mul表示已经分解出的数之积，Last表示最后一个分解出的数的值。
由于本题的数据范围为 N ≤ 100, 而 1 + 2 + .. + 14 > 100，最大迭代层数为14，所以暴力搜索的方法也能够通过。
然而本题还有一个非常巧妙的定理，让我们一起来探究一下吧。
在上面的算法中，我们总是在已经枚举出整个方案后，再对Mul是否能够整除 M 进行判定。那么是否能够在计算的过程中就进行判定呢？
假如Mul能够整除 M，则有 gcd(Mul,
M) = M (gcd(A,B)表示 A,B 的最大公约数)。
在不断迭代的过程中，gcd(Mul, M) 会怎样变化呢？
假设某一时刻gcd(Mul, M) = K，则有Mul =
_P * K_, _M = Q * K_，其中 P 与 Q 互质。
当我们新分解出一个数 L ，有：
gcd(Mul*L, M) = gcd(P
* K * L, Q * K) = K * gcd(P * L, Q) ≥ K
由于 P 与 Q 互质，所以我们可以得到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)是递增的，并且我们可以根据gcd(Mul,M)能够计算出gcd(Mul*L,M)。所以我们不再需要保存Mul，只需要记录gcd(Mul,
M)即可。
因此我们将DFS可以改进为：
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表示当前分解数之积与 M 的最大公约数，gcd(A,B)为求解 A,B 最大公约数的函数。
这样的改进并不能减少我们的时间复杂度，但是我们可以发现相对于DFS(N,M,Last,Sum,Mul)，DFS(N,M,Last,Sum,Gcd)中会出现的重复状态变多了。
在DFS(N,M,Last,Sum,Mul)和DFS(N,M,Last,Sum,Gcd)中，Last和Sum的值都在
0 .. N 范围内，而Mul的范围很大，Gcd的范围只在
0 .. M。
所以我们可以使用记忆化搜索来进行优化，减少重复的计算：
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。
此外在计算过程中，我们总是要计算gcd(Gcd * l, M)，而Gcd
* l的范围在 0 .. 5000，因此我们可以用一个数组gcd[i]预处理出所有的gcd(i,M)。
由于f的每一个状态只会计算一次，因此总的时间复杂度为_O(N^3*M)_，也就能够通过所有的数据。
记忆化搜索在很多时候是可以转变为动态规划的，这道题也不例外。
根据上面记忆化搜索的程序，我们可以得到一个动态规划的解法：
f[Sum + i][i][ gcd(Gcd * i, M) ] = f[Sum + i][i][ gcd(Gcd * i, M) ] + f[Sum][Last][Gcd];
在已经知道f[Sum][Last][Gcd]方案数的情况下，我们枚举下一个数i来进行递推。
初始化f数组为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;
本题主要的难点在于对于Gcd(Mul, M)的推导，然而出题人给出的数据范围太小，而使得不使用这一性质也能通过该题。
若将题目中条件从 0 < A1 < A2 < ... < Ak 改为 0 < A1 ≤ A2 ≤ ... ≤ Ak，此题的难度会提升很多，有兴趣的读者可以试一试求解。
下载文档
