No.520 An Invitation to Project Euler
タグ : / 解いたユーザー数 26
作問者 :
horiesiniti
/ テスター :
tubo28
Foreword
Project Euler is a competitive programming site specializing in problems of combinatorics and number theory. As befits a site with participants from all over the world, it is a great deal of fun: the solvers' forum, which only those who have answered correctly can view, is full of solutions in interesting languages you have never seen before. For example, if you do not know the J language, I recommend looking it up once. Almost all of its commands and operators are a single character, its operators use nearly every ASCII character, and writing two, three, or more operators in a row changes their meaning and order of application according to regular rules. J is a language you often see on Project Euler, and it is a fun language that changes your view of the world quite a bit when you study it.
Problem Statement
Project Euler had a problem along these lines. Let S be the set consisting of "the points placed on the 4 sides of a square so that each side is divided into n equal parts" and "the 4 vertices of the square". Choose 2 points of S and keep connecting 2 points of S, under the condition that each segment is drawn inside the quadrilateral. Keep drawing segments under the condition that they do not cross any segment drawn so far, until no more segments can be drawn. How many ways of drawing are there? Drawings that become identical under rotation or reflection are counted as distinct.Let us modify this problem a little. On the sides of an equilateral triangle ABC, add internal division points: a1 on side a, b1 on side b, and c1 on side c. Let U be the set consisting of the internal division points and the vertices of the triangle. Choose 2 points of U and keep drawing segments, under the condition that each segment is drawn inside the triangle and does not cross any segment drawn so far, until no more segments can be drawn. How many ways of drawing are there? Given a1, b1, c1, answer modulo 1000000007.
Two examples of ways of drawing the lines for a1=2, b1=3, c1=4 are shown above. In both figures, lines have been drawn until no more lines can be drawn. When the numbers of internal division points on sides a, b, c are fixed, how many ways are there to draw lines in this manner? The triangle is placed on the Euclidean plane with vertex A at the origin, side c on the X-axis, and the Y-coordinate of point C at least 0; ways of drawing that become identical by applying rotation or reflection are regarded as different ways of drawing.
Input
$n$ $a1$ $b1$ $c1$ $\dots$ $ai$ $bi$ $ci$ $\dots$ $an$ $bn$ $cn$
0 < $n$ <= 10
The number of triangle data sets.
Each data set of a triangle is given on one line.
0 < $ai$,$bi$,$ci$ <= 100
$ai$ is the number of internal division points on side a, $bi$ is the number of internal division points on side b, and $ci$ is the number of internal division points on side c.
For the given $ai$,$bi$,$ci$, let $Ansi$ be the number of ways of drawing the lines modulo 1000000007, and output each one on its own line.
Output
$Ans1$
$\dots$
$Ansi$
$\dots$
$Ansn$
Print a newline after each one.
Sample
Sample 1
Input
5 12 4 7 1 3 1 4 2 7 2 3 5 4 4 4
Output
2414171 11 2430 371 1847
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。