频次统计:设不同取值共有 m 种,第 i 种值的出现次数为 ni。
组合计数:选择两种不同的值 i=j,从其中一种取 3 个,另一种取 2 个。对固定的 (i,j),可行子序列数为 (3ni)(2nj)。对所有有序对求和,答案为
小红定义一个长度为 5 的数组是"葫芦”,当且仅当数组仅包含两种元素,其中一种出现次数为 2 ,另一种出现次数为 3 。例如、{1,1,4,1,4} 是葫芦,而 {1,2,3,4,5}、{6,6,6,6,6} 均不是葫芦。
现在小红拿到了一个数组,她想知道有多少长度为 5 的 子序列 是“葫芦”?
子序列 为从原数组中删除任意个(可以为零、可以为全部)元素得到的新数组。
第一行输入一个正整数 n(1≦n≦5000) ,代表数组的长度。
第二行输入 n 个正整数 a1,a2,...,an(1≦ai≦109) 代表数组的元素。
输出一个整数,代表“葫芦”的数量。
输入
6
1 1 4 5 1 4
输出
1
输入
6
1 1 4 4 4 1
输出
6