求大小为 K 的子数组的个数，其总和可被 M 整除？

Question

Alice 有N 个硬币，数量从 0 到(N-1)。鲍勃想从中取出k 个硬币，但爱丽丝只有在这组K 个硬币有趣的情况下才会给予。

如果一组硬币的总和可以被唯一整数M整除，那么它们就很有趣。现在鲍勃想知道他可以通过多少种方式获得K币。

按answer%(10^9+7)打印结果

输入格式：- 三个空格分隔的整数 N,K,M

限制：-

• 1 <= N，M <= 10 ^ 3
• 1 <= K <= 10 ^ 2

输入示例：- 4 2 2

示例输出：- 2({1,3},{2,4})

我尝试使用 python 库中的组合来解决问题，但结果超出了内存限制。 后来我用了递归的方法，但也导致超出了时间限制。因为每个私有测试用例需要 10 秒的时间。

任何人都可以帮助解决这种有效的方式吗？

递归方法的代码：

cou=0
n,k,m = input().split()
out_ = solve(k,m,n)
print(out_)


def getCombinations(data,n,k,m):
    val=[0]*k
    combiUtil(data,n,k,0,val,0,m)

def combiUtil(data,n,k,ind,val,i,m):
    global cou
    if(ind==k):
        if(sum(val)%m==0):
            cou+=1
        return
    if(i>=n):
        return
    val[ind]=data[i]
    combiUtil(data,n,k,ind+1,val,i+1,m)
    combiUtil(data,n,k,ind,val,i+1,m)

def solve(k,m,n):
    global cou
    k=int(k)
    m=int(m)
    n=int(n)
    ans =0
    data = [j for j in range(1,n+1)]
    getCombinations(data,n,k,m)   
    return cou%(10**9+7)

Answer 1

如果您查看“尝试所有组合”强力解决方案的时间复杂度，它等于O((N choose K) * K) = O(K * N^K)，因为有多种N choose K方法可以从包容性中选择K不同的整数1 to N，并且评估它们的总和需要K-1加法。N对于和的所有值（除了很小的值）而言K，这都是一个天文数字。

更好的解决方案：动态规划

一个更快且稍微简单的解决方案是动态编程。我们可以将其写为 3D 动态规划问题：

Let dp[i][j][r], 0 <= i <= N; 0 <= j <= K; 0 <= r < M
be the number of combinations of j ints from [1, 2, ..., i] 
with sum congruent to r modulo M. We want dp[N][K][0]

dp[i][j][r] = 1 if i == j == r == 0
              0 if i == 0 and (j /= 0 or r /= 0)
              1 if j == 0 and r == 0
              0 if j == 0 and r /= 0
              dp[i-1][j][r] + dp[i-1][j-1][(r-i) % M] otherwise

公式中添加了很多边缘情况，但最重要的方面是最后一种情况：我们的动态规划子问题最多依赖于 2 个其他子问题，因此总运行时间是我们的 DP 数组的大小：O(nmk)。这是一个 Python 实现：

def get_combinations_dp(max_part_size: int, total_num_parts: int, mod: int) -> int:
    BIG_MOD = 10 ** 9 + 7

    # Optimization if no partitions exist
    if total_num_parts > max_part_size:
        return 0

    largest_sum = ((max_part_size * (max_part_size + 1) // 2)
                   - ((max_part_size - total_num_parts) *
                      (max_part_size - total_num_parts + 1) // 2))
    # Optimization if largest partition sum still smaller than mod
    if largest_sum < mod:
        return 0

    dp = [[0 for _ in range(mod)] for _ in range(total_num_parts + 1)]
    dp[0][0] = 1

    for curr_max_part in range(1, max_part_size + 1):
        for curr_num_parts in reversed(range(0, total_num_parts)):
            for rem in range(mod):
                dp[curr_num_parts + 1][(rem + curr_max_part) % mod] += dp[curr_num_parts][rem]
                dp[curr_num_parts + 1][(rem + curr_max_part) % mod] %= BIG_MOD
    return dp[total_num_parts][0]

这些参数被N, K, M重命名为max_part_size, total_num_parts, mod，并带有一些可选的预检查，0以便在没有分区时立即返回。

现在，假设您想要做得更好O(nmk)。在这里，事情变得棘手。如果你想做得更好，我能想到的唯一方法是找到这些分区的生成函数，并使用 FFT 或其他一些快速多项式乘法模10**9 + 7。为了开始研究如何做到这一点，我建议数学堆栈交换上的这个线程，该线程涉及根据更知名的分区号精确计算这些分区，其生成函数是已知的。即便如此，我也找不到任何关于该生成函数是否具有简短表示的提及，并且直接使用分区号无法提高复杂性O(nmk)。

使用组合学

如果您仍然想使用这种动态编程方法，可以使用组合数学进行一个小修改，当N大于 时，组合数学可能会渐近更快M*K：它及时运行O((M*K)^2)，不依赖于N。这个想法是使用我们的 DP 公式，但[1, ... N]我们现在不是从 中选择 K 个不同的整数，而是从 中选择 K 个（可能重复的）残基类[0, ... M-1]。

这是如何运作的？首先，我们需要计算有多少个整数[1, ... N]属于每个残基类别i mod M。拨打这个号码R[i]，为0 <= i < M。您可以将其计算为

R[i] = floor(N/M) + (1 if 0 < i <= N%M else 0)

现在我们可以编写一个稍加修改的动态规划定义和公式：

R[i] = floor(N/M) + (1 if 0 < i <= N%M else 0)

Answer 2

我希望您可能已经解决了这个问题。但尽管如此，我还是为那些觉得有帮助的人回答这个问题。

您尝试过自己获取组合，但您可以使用库来获取所有可能的组合，然后简单地迭代并检查条件。如果目的不仅仅是为了学习，那么使用已经可用的代码总是可以的。

不管怎样，还是看一下代码吧。谢谢。

from itertools import combinations
def getCombi(n, k, m):
    count = 0
    #Required Combinations
    reqcombis = []
    array = [i for i in range(1, n+1)]
    #getting all possible combinations
    totalcombins = combinations(array, k)
    for i in totalcombins:
        if sum(i) % m == 0 and sum(i) <= n:
            count+=1
            reqcombis.append(i) 
    return count, reqcombis

if __name__ == "__main__":
    n, k, m = input().split(",")
    n, k, m = int(n), int(k), int(m)
    print(getCombi(n, k, m))