問題一覧 > 通常問題

No.118 門松列(2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 258
作問者 : yuki2006
2 ProblemId : 221 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:37:13

問題文

玄関に飾る門松を作っている時に、あることに気づいた。

N本の竹を高さをそれぞれAiとしたときに、
それらから3本を自由に選んでよく、自由に並び替えて良い。
その時に何組の選び方の数が「門松列」になっているかを知りたくなった。

「門松列」とは、選んだ「3つの竹の長さの降順で2番目が、左または右側になっているもの」、「3つの長さはすべて異なる」という条件も満たすものであるとする。

N本の竹の高さが与えられるので、「門松列」にすることができる3つの竹の選び方の数を求めてください。
(並び順が違っても、同じ竹の組み合わせなら同じとカウントする。)

答えの数がintより多くなるので、(longよりは大きくならないようです)その値をmod 109+7で求めてください。

それぞれの竹は番号が振ってあるので区別ができるとする。

入力

N
A1 A2AN

入力は全て整数で与えられる。
3N100000=105
1Ai100=102,1iN

出力

「門松列」になる組み合わせ数をmod 109+7で求めてください。

サンプル

サンプル1
入力
3
1 2 3
出力
1

この3つの竹で門松列を作ることができます。

サンプル2
入力
6
1 2 2 3 3 3
出力
6

長さ2の竹,長さ3の竹はそれぞれ区別できるので、6種類の選び方があるようです。

サンプル3
入力
10
13 54 87 47 99 33 2 56 95 85
出力
120

この場合、10C3と同じになります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。