B - Makes And The Product CodeForces

B - Makes And The Product CodeForces - 817B（组合数）

本文主要是介绍B - Makes And The Product CodeForces - 817B（组合数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

After returning from the army Makes received a gift — an array a consisting of n positive integer numbers. He hadn’t been solving problems for a long time, so he became interested to answer a particular question: how many triples of indices (i, j, k) (i < j < k), such that ai·aj·ak is minimum possible, are there in the array? Help him with it!

Input
The first line of input contains a positive integer number n (3 ≤ n ≤ 105) — the number of elements in array a. The second line contains n positive integer numbers ai (1 ≤ ai ≤ 109) — the elements of a given array.

Output
Print one number — the quantity of triples (i, j, k) such that i, j and k are pairwise distinct and ai·aj·ak is minimum possible.

Examples
Input
4
1 1 1 1
Output
4
Input
5
1 3 2 3 4
Output
2
Input
6
1 3 3 1 3 2
Output
1
Note
In the first example Makes always chooses three ones out of four, and the number of ways to choose them is 4.

In the second example a triple of numbers (1, 2, 3) is chosen (numbers, not indices). Since there are two ways to choose an element 3, then the answer is 2.

In the third example a triple of numbers (1, 1, 2) is chosen, and there’s only one way to choose indices.

题意： 不同坐标三个数相乘得到的最小值，有多少种选法
思路： 组合数？不过本题只需要排序以后选前3个数，那么选法变多只有可能第三个数多了很多相同的情况。不过怕漏选，直接全部考虑了一下，然后套组合数公式即可

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>using namespace std;
typedef long long ll;const int maxn = 2e5 + 7;
ll a[maxn];
map<ll,int>mp;ll C[maxn][10];
const int N = 100000 + 5;
const ll MOD = (int)1e18 + 7;
void init()
{C[1][0] = C[1][1] = 1;for (int i = 2; i < N; i++){C[i][0] = 1;for (int j = 1; j < 6; j++)C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);}
}int main()
{init();int n;scanf("%d",&n);for(int i = 1;i <= n;i++){scanf("%lld",&a[i]);mp[a[i]]++;}sort(a + 1,a + 1 + n);ll ans = 0;if(a[1] != a[2] && a[1] != a[3] && a[2] != a[3]){ans = mp[a[1]] * mp[a[2]] * mp[a[3]];printf("%lld\n",ans);}else if(a[1] == a[2] && a[2] == a[3]){int num = mp[a[1]];printf("%lld\n",C[num][3]);}else if(a[1] == a[2]){int num = mp[a[1]];ll ans = C[num][2];ans *= 1ll * mp[a[3]];printf("%lld\n",ans);}else if(a[2] == a[3]){int num = mp[a[2]];ll ans = C[num][2];ans *= 1ll * mp[a[1]];printf("%lld\n",ans);}else if(a[1] == a[3]){int num = mp[a[1]];ll ans = C[num][2];ans *= 1ll * mp[a[2]];printf("%lld\n",ans);}return 0;
}