問題一覧 > 通常問題

No.520 プロジェクトオイラーへの招待

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : 👑 horiesinitihoriesiniti / テスター : tubo28tubo28
2 ProblemId : 1212 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-05-28 22:27:41

前説

プロジェクトオイラーとは組み合わせ論や整数論の問題に特化した競技プログラムのサイトです。 世界中から参加者が集まるサイトだけあって正答者だけが見れる正答者掲示板には見たこともない面白い言語での解法がたくさん掲載されている非常に楽しいサイトです。 例えばあなたがJ言語という言語を知らなければ一度調べてみることをお勧めします。 ほとんどの命令語と演算子が一文字で、演算子はほぼすべてのアスキーコードを使い、演算子を2つ以上3つ以上それ以上続けて書くと規則的に演算子の意味や適用順序が変わったりします。 プロジェクトオイラーではj言語はよく見かける言語なのですが、勉強してみると世界観がかなりかわる楽しい言語です。

問題文

プロジェクトオイラーにこんな感じの問題がありました。 ”正方形の各辺をn等分する形で4辺につけた点”と”正方形の4頂点”を集めた点の集合をSとします。 Sの2点を選び四角形の中にひかれる線分という条件でSの2点をどんどん結んでいきます。 今までに引いた線分と交差しないという条件でどんどん線分を引いていきこれ以上引けなくなるまで線分を引いていきます。 このとき何通りの引き方があるだろうか? 回転や反転して同じになるものは別として数える。

この問題を少し変更してみます。 正3角形ABCの各辺に、辺aにa1個,辺bにb1個,辺cにc1個の内分点を追加します。 内分点と三角形の頂点を合わせた点の集合をUとします。 Uの2点を選び、三角形の中に引かれる線分かつ今までに引いた線分と交差しないという条件でどんどん線分を引いていきこれ以上引けなくなるまで線分を引いていきます。 このとき何通りの引き方があるだろうか? a1,b1,c1が与えられるので1000000007で割った余りで答えよ。

a1=2個,b1=3,c1=4での線の引き方の例を2つ掲載してみました。 どちらの図もこれ以上線は引けないところまで線を引いています。 辺a,b,cにつける内分点の数が決まった時このように線を引く方法は何通りあるだろうか? 三角形はユークリッド平面上で頂点Aを原点に、辺cをX軸に、点CのY座標が0以上になるように配置し、回転や反転を適用して同じになる線の引き方は違う線の引き方と解釈する。

入力

$n$
$a1$ $b1$ $c1$
$\dots$
$ai$ $bi$ $ci$
$\dots$
$an$ $bn$ $cn$

0 < $n$ <= 10 三角形のデータの個数。 三角形の一つのデータセットは一行ずつ与えられる。 0 < $ai$,$bi$,$ci$ <= 100
$ai$は辺aの内分点の数、$bi$は辺bの内分点の数、$ci$は辺cの内分点の数。
$ai$,$bi$,$ci$が決まった時何通りの線の引き方があるか10億7で割ったあまりを$Ansi$通りとして一行ずつ出力せよ。

出力

$Ans1$
$\dots$
$Ansi$
$\dots$
$Ansn$
一つずつ改行してください。

サンプル

サンプル1
入力
5
12 4 7
1 3 1
4 2 7
2 3 5
4 4 4
出力
2414171
11
2430
371
1847

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