时间戳

首页 > 解决方案 > 计算 A 的子序列的数量，使得子序列的每个元素都可以被它的索引整除（从 1 开始）

algorithm - 计算 A 的子序列的数量，使得子序列的每个元素都可以被它的索引整除（从 1 开始）

问题描述

B 是 A 的子序列当且仅当我们可以通过删除零个或多个元素将 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},{2,22},{2,14},{2},{2,22},{2,14},{1},{1,22},{1 ,14},{22},{22,14},{14}

我的尝试：

我能想出的唯一解决方案很O(n^2)复杂。

标签： algorithmdynamic-programming

解决方案

假设 中的最大元素A为C，以下是具有时间复杂度的算法O(n * sqrt(C))：

  1. 对于 中的每个元素x，A找到 的所有除数x。
  2. 对于i从 1 到的每一个，使用步骤 1 的结果n找到每一个是 的倍数的j这样。A[j]i
  3. 对于每一个i从 1 到n和j这样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)

推荐阅读