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

Question

Alice has N coins of amount from 0 to (N-1). Bob wants to take k coins out of them, but Alice will only give if the set of K coins is interesting.

A set of coins is interesting if the sum of them is divisible by a unique integer M. Now Bob wants to know in how many ways he can get K coins.

Print the result by answer%(10^9+7)

Input format:- Three space separated integers N,K,M

Constraints:-

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

Sample input:- 4 2 2

Sample output:- 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种方法从1 to N中选择K个不同的整数，计算它们的和需要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。首先，我建议使用math stackexchange上的this thread来研究如何做到这一点，这涉及到根据更为知名的分区号精确计算这些分区，其生成函数已经为人所知。即使如此，我也找不到任何关于生成函数是否具有短表示的内容，直接使用分区号并不能改善O(nmk)的复杂性

使用组合数学

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

这是怎么回事？首先，我们需要计算[1, ... N]中有多少整数属于每个剩余类i mod M。打这个电话R[i]，换成0 <= i < M。你可以这样计算

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

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

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

dp[i][j][r] = 1 if i == j == r == 0
              0 if i == 0 and (j /= 0 or r /= 0)
              0 if i < 0 or j < 0
              F(i, j, r) otherwise

F(i, j, r) = Sum from p = 0 to min(R[i], j) of:
(R[i] choose p) * dp[i-1][j-p][(r - i*p) % M]

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))

Answer 3

@kcsquared解决方案的三个NumPy版本，可在10秒时间限制内轻松解决最坏情况：

def numpy1(n, k, m):
    dp = np.zeros((k+1, m), np.int32)
    dp[0][0] = 1
    for i in range(1, n+1):
        dp[1:,] += dp[:-1, (np.arange(m) + i) % m]
        dp %= 10**9 + 7
    return dp[k][0]

def numpy2(n, k, m):
    dp = np.zeros((k+1, m), np.int32)
    dp[0][0] = 1
    i = range(m)
    for _ in range(n):
        i = np.roll(i, 1)
        dp[1:,] += dp[:-1, i]
        dp %= 10**9 + 7
    return dp[k][0]

def numpy3(n, k, m):
    dp = np.zeros((k+1, m), np.int32)
    dp[0][0] = 1
    for i in range(n):
        dp[1:,] += np.roll(dp[:-1,], i, axis=1)
        dp %= 10**9 + 7
    return dp[k][0]

中小企业和最坏情况的基准：

n = 19   k = 11   m = 13
                           -
22856.8 μs  23409.3 μs  23421.4 μs  naive
  496.9 μs    500.2 μs    524.7 μs  dtjc
  918.6 μs    928.6 μs    936.3 μs  kcsquared
  173.5 μs    183.6 μs    191.9 μs  numpy1
  402.2 μs    403.5 μs    411.1 μs  numpy2
  297.8 μs    318.4 μs    320.1 μs  numpy3

n = 200   k = 100   m = 200
                           -
2033.6 ms  2177.3 ms  2178.1 ms  dtjc
1410.6 ms  1420.2 ms  1430.5 ms  kcsquared
  19.5 ms    19.8 ms    20.3 ms  numpy1
  22.5 ms    22.9 ms    23.0 ms  numpy2
  26.8 ms    27.3 ms    27.3 ms  numpy3

n = 1000   k = 100   m = 1000
                           -
508.0 ms  516.1 ms  519.2 ms  numpy1
518.3 ms  518.8 ms  526.3 ms  numpy2
495.1 ms  496.4 ms  499.2 ms  numpy3

基准代码（Try it online!）：

from timeit import repeat
from itertools import combinations
from functools import lru_cache
import numpy as np

def naive(n, k, m):
    return sum(sum(combi) % m == 0
               for combi in combinations(range(1, n+1), k)) % (10**9 + 7)

@lru_cache(None)
def dtjc(n, k, m, r=0):
    if k > n:
        return 0
    if k == 0:
        return 1 if r == 0 else 0
    return (dtjc(n-1, k, m, r) + dtjc(n-1, k-1, m, (r+n) % m)) % (10**9 + 7)

def kcsquared(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]

def numpy1(n, k, m):
    dp = np.zeros((k+1, m), np.int32)
    dp[0][0] = 1
    for i in range(1, n+1):
        dp[1:,] += dp[:-1, (np.arange(m) + i) % m]
        dp %= 10**9 + 7
    return dp[k][0]

def numpy2(n, k, m):
    dp = np.zeros((k+1, m), np.int32)
    dp[0][0] = 1
    i = range(m)
    for _ in range(n):
        i = np.roll(i, 1)
        dp[1:,] += dp[:-1, i]
        dp %= 10**9 + 7
    return dp[k][0]

def numpy3(n, k, m):
    dp = np.zeros((k+1, m), np.int32)
    dp[0][0] = 1
    for i in range(n):
        dp[1:,] += np.roll(dp[:-1,], i, axis=1)
        dp %= 10**9 + 7
    return dp[k][0]

def test(args, solutions, number, format_time):
    print('n = %d   k = %d   m = %d' % args)
    print('-' * 55)
    for _ in range(1):
        results = set()
        for func in solutions:
            times = sorted(repeat(lambda: dtjc.cache_clear() or results.add(func(*args)), number=number))[:3]
            print(*(format_time(t / number) for t in times), func.__name__)
        print('results set:', results)
        assert len(results) == 1
        print()

test((19, 11, 13),
     [naive, dtjc, kcsquared, numpy1, numpy2, numpy3],
     10,
     lambda time: '%7.1f μs ' % (time * 1e6))
test((200, 100, 200),
     [dtjc, kcsquared, numpy1, numpy2, numpy3],
     1,
     lambda time: '%6.1f ms ' % (time * 1e3))
test((1000, 100, 1000),
     [numpy1, numpy2, numpy3],
     1,
     lambda time: '%5.1f ms ' % (time * 1e3))