23660: 7的倍数取法有多少种

dfs, dp, http://cs101.openjudge.cn/practice/23660/

在n个不同的正整数里，任意取若干个，不能重复取,要求它们的和是7的倍数，问有几种取法。

输入

第一行是整数t，表示有t组数据(t<10)。接下来有t行，每行是一组数据，每组数据第一个数是n（1 <= n <= 16），表示要从n个整数里取数,接下来就是n个整数。

输出

对每组数据，输出一行，表示取法的数目（一个都不取也算一种取法）。

样例输入

3
3 1 2 4
5 1 2 3 4 5
12 1 2 3 4 5 6 7 8 9 10 11 12

样例输出

2
5
586

来源：郭炜

这是一个组合问题，可以使用递归的方式来解决。

首先，定义一个递归函数 count_combinations，接受三个参数：当前位置 index，当前和 current_sum，以及取法数目 count。在每一次递归调用中，我们有两种选择：取当前位置的数或者不取。如果取了当前位置的数，那么递归调用时更新 index 为下一个位置，current_sum 加上当前位置的数值，并且 count 不变。如果不取当前位置的数，那么递归调用时更新 index 为下一个位置，current_sum 不变，并且 count 不变。递归的终止条件是当 index 超过了数组的长度时，我们检查 current_sum 是否是7的倍数。如果是，就将 count 加1。

下面是相应的实现：

def count_combinations(numbers, index, current_sum, count):
    if index >= len(numbers):
        if current_sum % 7 == 0:
            return count + 1
        else:
            return count
    
    # 选择取当前位置的数
    count = count_combinations(numbers, index + 1, current_sum + numbers[index], count)
    
    # 选择不取当前位置的数
    count = count_combinations(numbers, index + 1, current_sum, count)
    
    return count


# 主程序
t = int(input())
for _ in range(t):
    data = list(map(int, input().split()))
    n = data[0]
    numbers = data[1:]
    
    result = count_combinations(numbers, 0, 0, 0)
    print(result)

对于给定的每组数据，我们调用 count_combinations 函数，初始时 index 为0，current_sum 为0，count 为0。然后打印最终的结果即可。

针对这个问题，可以使用动态规划来优化计算过程，避免重复计算。

我们可以使用一个二维数组 dp 来记录每个位置的状态。dp[i][j] 表示从前 i 个数中选取若干个数，它们的和对 7 取余等于 j 的取法数目。

动态规划的状态转移方程如下：

dp[i][j] = dp[i-1][(j - numbers[i]) % 7] + dp[i-1][j]

其中 numbers[i] 表示第 i 个数。

下面是相应的实现：

# 主程序
t = int(input())
for _ in range(t):
    data = list(map(int, input().split()))
    n = data[0]
    numbers = data[1:]
    
    # 初始化动态规划数组
    dp = [[0] * 7 for _ in range(n+1)]
    dp[0][0] = 1
    
    for i in range(1, n+1):
        for j in range(7):
            dp[i][j] = dp[i-1][(j - numbers[i-1]) % 7] + dp[i-1][j]
    
    result = dp[n][0]
    print(result)

使用动态规划的方法，时间复杂度为 O(n*7)，其中 n 是数字的个数。相比于递归的方法，动态规划可以避免重复计算，提高了算法的效率。

进一步优化

# 主程序
t = int(input())
for _ in range(t):
    data = list(map(int, input().split()))
    n = data[0]
    numbers = data[1:]
    
    # 初始化动态规划数组
    dp = [[0] * 7 for _ in range(n+1)]
    dp[0][0] = 1
    
    for i in range(1, n+1):
        for j in range(7):
            dp[i][j] = dp[i-1][(j - numbers[i-1]%7 + 7) % 7] + dp[i-1][j]
    
    result = dp[n][0]
    print(result)