hiho一下第70周《Divided Product》题目分析

8
6

题意分析

给定正整数 N, M,将 N 分解为若干个正整数 A1, A2, ..., Ak,使得:

  • 0 < A1 < A2 < ... < Ak
  • A1 + A2 + ... + Ak = N
  • A1 * 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_,其中 PQ 互质。

当我们新分解出一个数 L ,有:

gcd(Mul*L, M) = gcd(P * K * L, Q * K) = K * gcd(P * L, Q)K

由于 PQ 互质,所以我们可以得到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)中,LastSum的值都在 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,此题的难度会提升很多,有兴趣的读者可以试一试求解。

4 answer(s)

0

在gtdzx的启发下,在搜索过程中记录Mul % M,而非gcd(Mul, M),同样可以解决本题,且更为容易想到。

int dfs(int curr_sum, int last, int curr_mod)
{
    if (dp[curr_sum][last][curr_mod] != -1)
        return dp[curr_sum][last][curr_mod];
    if (curr_sum == n)
        return curr_mod == 0 ? 1 : 0;
    int cnt = 0;
    for (int i = last + 1; i <= n - curr_sum; ++i)
        cnt = (cnt + dfs(curr_sum + i, i, (curr_mod * i) % m)) % 1000000007;
    dp[curr_sum][last][curr_mod] = cnt;
    return cnt;
}
0

这道题还是可以用DP来解决的。 如果数值真的变大,你的这个暴力DFS方法会超时

0

如果改成可以相等的话是不是在最后一层循环中l从j开始就可以了呢?

1

1000000007什么意思

  • 又是答案非常大,可能无法用int或long long装载,由于考的只是算法,故就不考虑大数的情况,所以讲答案确定在一个范围内,有利于编程者更好的做题!

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享