No.118 Kadomatsu Sequence (2)
タグ : / 解いたユーザー数 274
作問者 :
Problem Statement
While making a kadomatsu to decorate the entrance, I noticed something.
Given $N$ bamboo stalks with heights $A_i$,
you may freely choose $3$ of them and freely rearrange them.
I became curious how many of the ways of choosing form a "Kadomatsu Sequence".
A "Kadomatsu Sequence" is defined as one that satisfies both of the conditions "among the $3$ chosen bamboo stalks, the $2$nd in descending order of length is on the left or right side" and "the $3$ lengths are all different".
Given the heights of the $N$ bamboo stalks, find the number of ways to choose 3 bamboo stalks that can form a "Kadomatsu Sequence".
(The same combination of bamboo stalks is counted as the same, even if the order differs.)
Since the answer can exceed the range of int (though it apparently does not exceed that of long), find the value $\rm mod\ 10^9+7$.
Each bamboo stalk is numbered, so they are distinguishable.
Input
$N$ $A_1\ A_2 \dots A_N$
All inputs are given as integers.
$3\le N \le 100000=10^5$
$1\le A_i \le 100=10^2,1\le i \le N$
Output
Output the number of combinations that form a "Kadomatsu Sequence", $\rm mod\ 10^9+7$.
Sample
Sample 1
Input
3 1 2 3
Output
1
These 3 bamboo stalks can form a Kadomatsu Sequence.
Sample 2
Input
6 1 2 2 3 3 3
Output
6
The bamboo stalks of length 2 and those of length 3 are each distinguishable, so there appear to be 6 ways of choosing.
Sample 3
Input
10 13 54 87 47 99 33 2 56 95 85
Output
120
In this case, the answer is the same as ${}_{10} C_3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。