題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC439D Kadomatsu Subsequence

Problem Statement

題目簡述

給定長度為 $N$ 的整數序列 $A$ ，求滿足以下條件的三元組 $(i, j, k)$ 數量：

$A_i : A_j : A_k = 7 : 5 : 3$
$j = \min(i, j, k)$ 或 $j = \max(i, j, k)$ （即 $j$ 是三者中最小或最大的索引）

Constraints

約束條件

$1 \le N \le 3 \times 10^5$
$1 \le A_i \le 10^9$

思路：前後綴分解

問題轉化

比值條件 $A_i : A_j : A_k = 7 : 5 : 3$ 意味著存在某個正整數 $v$ ，使得：

$A_i = 7v$
$A_j = 5v$
$A_k = 3v$

而位置條件「 $j$ 是三者中最小或最大」可分為兩種情況：

$j$ 最大： $j > i$ 且 $j > k$ ，即 $A_i$ 和 $A_k$ 都在 $A_j$ 之前
$j$ 最小： $j < i$ 且 $j < k$ ，即 $A_i$ 和 $A_k$ 都在 $A_j$ 之後

前綴計數

對於情況 1（ $j$ 最大），我們從左到右掃描陣列：

維護 pre7[v]：目前為止 $A_i = 7v$ 的元素個數
維護 pre3[v]：目前為止 $A_k = 3v$ 的元素個數
當遇到 $A_j = 5v$ （即 $A_j$ 是 5 的倍數）時，答案增加 pre7[v] * pre3[v]

利用對稱性

對於情況 2（ $j$ 最小），只需反轉陣列後重複相同的計算即可。

反轉後，原本在 $j$ 之後的元素變成在 $j$ 之前，問題結構完全相同。

複雜度分析

時間複雜度： $\mathcal{O}(N)$ ，掃描兩次陣列，每次操作為 $O(1)$ 的 HashMap 操作
空間複雜度： $\mathcal{O}(N)$ ，HashMap 最多儲存 $N$ 個不同的 $v$ 值

Code

from collections import defaultdict

def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    def do(A):
        ans = 0
        pre3 = defaultdict(int)
        pre7 = defaultdict(int)
        for x in A:
            if x % 5 == 0:
                v = x // 5
                ans += pre7[v] * pre3[v]
            if x % 3 == 0:
                pre3[x // 3] += 1
            if x % 7 == 0:
                pre7[x // 7] += 1
        return ans

    print(do(A) + do(A[::-1]))

if __name__ == "__main__":
    solve()