1000ms

Difficulty: 6

所属公司 : 字节

时间 :2025年8月17日

算法与标签>组合计数

会员或题库专享

请先，开通会员或购买题库字节跳动机考题库，可解锁完整内容。

购买字节跳动机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（字节跳动机考题库），可解锁完整内容。

购买题库开通会员

思路

频次统计：设不同取值共有 $m$ 种，第 $i$ 种值的出现次数为 $n_i$ 。
组合计数：选择两种不同的值 $i\ne j$ ，从其中一种取 $3$ 个，另一种取 $2$ 个。对固定的 $(i,j)$ ，可行子序列数为 $\binom{n_i}{3}\binom{n_j}{2}$ 。对所有有序对求和，答案为

题目内容

我们称一个长度为 $5$ 的序列是“双子序列”，当且仅当它恰好包含两种不同的数值，其中一种数值恰好出现了 $2$ 次，另一种数值恰好出现了 $3$ 次。例如， $[4, 4, 7, 4, 7]$ 是双子序列，而 $[1,2,3,4,5]$ 和 $[6,6,6,6,6]$ 都不是。

现在给定一个长度为 $n$ 的数组，请你计算该数组有多少个长度为 $5$ 的子序列是双子序列。在这里，子序列是指从原数组中删除任意个（可以为 $0$ 个，也可以全部）元素后所得到的新序列，且原数组中不同位置的相同数值被视为不同的元素。

数组的长度 $n$ 满足 $1 \le n \le 5000$ ，数组中的所有元素均为正整数且不超过 $10^9$ 。

输入描述

第一行输入一个整数 $n$ ，表示数组的长度。第二行输入 $n$ 个由空格分隔的整数，依次表示数组中的元素。