计算A的子序列的个数，使子序列的每个元素都能被它的索引整除(从1开始)

Question

B是a的子序列，当且仅当移除0个或多个元素使a变为B

A = [1,2,3,4]
B = [1,4] is a subsequence of A.(Just remove 2 and 4).
B = [4,1] is not a subsequence of A.

计算A满足此条件的所有子序列:A[i]%i = 0

注意i从1开始不是0。

的例子:

Input : 
5
2 2 1 22 14
Output:
13

这13个子序列都满足B[i]%i = 0的条件。

{2},{2,},{2, 22},{2, 14},{2},{2, 22},{2, 14},{1},{1, 22},{1, 14},{22},{22日14},{14}

My attempt:

我能想到的唯一解决方案是O(n^2)复杂性。

Answer 1

假设A中的最大元素为C，则为时间复杂度为O(n * sqrt(C))的算法:

1. 对于A中的每个元素x，求x的所有因数
2. 对于从1到n的每个i，使用步骤1的结果，找出每个j，使A[j]是i的倍数。
3. 对于从1到n和j的每一个i,A[j]是i的倍数(使用步骤2的结果)，求B有i个元素的个数，最后一个元素是A[j](动态规划)。

def find_factors(x):
"""Returns all factors of x"""
for i in range(1, int(x ** 0.5) + 1):
if x % i == 0:
yield i
if i != x // i:
yield x // i
def solve(a):
"""Returns the answer for a"""
n = len(a)
# b[i] contains every j such that a[j] is a multiple of i+1.
b = [[] for i in range(n)]
for i, x in enumerate(a):
for factor in find_factors(x):
if factor <= n:
b[factor - 1].append(i)
# There are dp[i][j] sub arrays of A of length (i+1) ending at b[i][j]
dp = [[] for i in range(n)]
dp[0] = [1] * n
for i in range(1, n):
k = x = 0
for j in b[i]:
while k < len(b[i - 1]) and b[i - 1][k] < j:
x += dp[i - 1][k]
k += 1
dp[i].append(x)
return sum(sum(dpi) for dpi in dp)

Answer 2

对于A[i]的每一个因数d，其中d大于1且不大于i+1，则A[i]可以是d-1已计数子序列数的d元素。

JavaScript代码:

function getDivisors(n, max){
let m = 1;
const left = [];
const right = [];

while (m*m <= n && m <= max){
if (n % m == 0){
left.push(m);

const l = n / m;

if (l != m && l <= max)
right.push(l);
}

m += 1;
}

return right.concat(left.reverse());
}

function f(A){
const dp = [1, ...new Array(A.length).fill(0)];

let result = 0;

for (let i=0; i<A.length; i++){
for (d of getDivisors(A[i], i+1)){
result += dp[d-1];
dp[d] += dp[d-1];
}
}

return result;
}

var A = [2, 2, 1, 22, 14];
console.log(JSON.stringify(A));
console.log(f(A));

Answer 3

我认为对于一般情况，我们无法证明找到复杂度小于O(n^2)的算法。

首先，一个直观的解释:

让我们用a1, a2, a3, ..., a_n来表示数组的元素。

如果元素a1出现在子数组中，它必须是元素no。1 .

如果元素a2出现在子数组中，它可以是元素no。1或2.

如果元素a3出现在子数组中，它可以是元素no。1、2或3.

…

如果元素a_n出现在子数组中，它可以是元素no。1,2,3，…n .

因此，考虑到所有的可能性，我们必须执行以下测试:

检查a1是否能被1整除(当然是微不足道的)

检查a2是否能被1或2整除

检查a3是否能被1、2或3整除

…

检查a_n是否能被1,2,3，…整除n

总而言之，我们必须执行1+ 2 + 3 + ... + n = n(n - 1) / 2测试，其复杂度为O(n^2)。

请注意，上面的说法有些不准确，因为并非所有的测试都是严格必要的。例如，如果a_i能被2和3整除，那么它一定能被6整除。尽管如此，我认为这给了一个很好的直觉。

现在是一个更正式的论证:

定义一个数组:

a1 = 1

a2 = 1× 2

a3 = 1× 2 × 3

…

a_n = 1 × 2 × 3 × ... × n

根据定义，每个子数组都是有效的。

现在设(m, p)使m <= n和p <= n and changea_mtoa_m/p '。现在我们可以从以下两个路径中选择一个:

1. 如果我们限制p为素数，那么每个元组(m, p)代表一个强制测试，因为a_m值的相应变化改变了有效子数组的数量。但这需要对1到n之间的每个数进行质因数分解。用已知的方法，我认为我们不可能得到复杂度低于O(n^2)的结果。

2. 如果我们忽略上述限制，那么我们显然执行n(n - 1) / 2测试，这给出了O(n^2)的复杂度。