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)復雜的。
uj5u.com熱心網友回復：
假設 中的最大元素A為C，以下是時間復雜度為 的演算法O(n * sqrt(C))：
- 對于每一個元素
x中A，找到所有除數x。 - 對于
i從 1 到 的n每一個，使用步驟 1 的結果找出是 的倍數的每一個j這樣的。A[j]i - 對于每一個
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)
uj5u.com熱心網友回復：
對于每一個除數d的A[i]，其中d大于1且至多i 1，A[i]可以是d已經計數子序列的數目的第i個元素d-1。
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));uj5u.com熱心網友回復：
我相信，對于一般情況，我們無法證明找到復雜度小于 的演算法O(n^2)。
先來個直觀的解釋：
讓我們用 表示陣列的元素a1, a2, a3, ..., a_n。
如果元素a1出現在子陣列中，則它必須是元素編號。1.
如果元素a2出現在子陣列中，則可以是元素編號。1 或 2。
如果元素a3出現在子陣列中，則可以是元素編號。1、2 或 3。
...
如果元素a_n出現在子陣列中，則可以是元素編號。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 change a_m toa_m / p`。我們現在可以選擇以下兩條路徑之一：
如果我們限制
p為素數，那么每個元組都(m, p)代表一個強制測驗，因為相應的值a_m變化會改變有效子陣列的數量。但這需要對 1 和 之間的每個數字進行質因數分解n。通過已知的方法，我認為我們無法獲得小于O(n^2).如果我們省略上述限制，那么我們顯然會執行
n(n - 1) / 2測驗，這給出了O(n^2).
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335893.html