具有整数平均值的非空子序列的计数

Question

是否有任何算法可以用整数平均值来计算数组的非空子序列的数量，除了暴力方式？有dp解决方案吗？

例如 {2, 6, 2} 我们有 6 个具有整数平均值的子序列。

1. 2
2. 6
3. 2
4. 2 6
5. 6 2
6. 2 2

我尝试了暴力方法，但我想要使用 DP 的更好算法。

Answer 1

这是一个简单的

O(n^4)

算法。

def integer_average_subsequences (items):
    answer = 0
    for l in range(1, len(items)+1):
        counts = [[0] * l for _ in range(l+1)]
        counts[0][0] = 1
        for item in items:
            for j in range(l, 0, -1):
                for k in range(l):
                    counts[j][(k + item) % l] += counts[j-1][k]
        answer += counts[l][0]
    return answer

为每个长度重做 DP 似乎很浪费。但如果总和超过

O(n^2)

，这样做实际上会更快。