| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
ACM_0192 - CATALAN SQUARE |
Last weekend you and your friends went to visit the local farmer’s market at the town square. As you were standing around in a circle talking, you couldn’t help overhearing two of your friends musing over what sounded like an interesting problem: They were consid- ering the number of ways in which you could all shake hands, such that everyone in the circle simultaneously shaked hands with one other person, but where no arms crossed each other.
After a few seconds’ thought you decided to join your two friends, to share (with them) the solution to their problem. “If we are 2n persons”, you said, “pick any particular person, and let that person shake hands with somebody. That person will have to leave an even number of people on each side of the person with whom he/she shakes hands. Of the remaining n − 1 pairs of people, he/she can leave zero on the right and n − 1 pairs on the left, 1 on the right and n − 2 pairs on the left, and so on. The pairs remaining on the right and left can independently choose any of the possible non-crossing handshake patterns, so the count Cn for n pairs of people is given by:
Cn = Cn−1C0 + Cn−2C1 + . . . + C1Cn−2 + C0Cn−1,
which, together with the fact that C0 = C1 = 1, is just the definition of the Catalan numbers.” By consulting your handy combinatorics book, you find out that there is a much more efficient formula for calculating Cn, namely:
After a collective groan from the group, your particularly cheeky friend Val called out “Well, since we are at the town square, why don’t you try to square your Catalan numbers!”. This was met with much rejoicing, while you started to think about how to square the Catalan sequence. . .
Task
Let Cn be the nth Catalan number as defined above. By regarding the sequence (Cn)n≥0 of Catalan numbers, we can define a sequence (Sn)n≥0, corresponding to “squaring the Catalan sequence”, by considering the Cauchy product, or discrete convolution, of (Cn)n≥0 with itself, i.e.,
Your task is to write a program for calculating the number Sn.
Input
The input contains one line containing one non-negative integer: n, with 0 ≤ n ≤ 5 000.
Output
Output a line containing Sn.
Examples
|
№ |
stdin |
stdout |
|
1 |
0 |
1 |
|
2 |
59 |
1583850964596120042686772779038896 |
| Ավելացրեց. | Հրանտ Հովհաննիսյան |
| Ամսաթիվ. | 2014-10-08 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE |
| Աղբյուրը. | Nordic (NCPC) 2014.C |
RSS