CONNECTE - Connected Points
English | Vietnamese |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/connecte
Cho lưới 3 × N điểm. Mỗi điểm có tối đa 8 điểm xung quanh.
Người ta nối các điểm của lưới tạo thành một đường gấp khúc khép kín với các tính chất sau:
- Đường gấp khúc chứa tất cả 3 × N điểm của lưới.
- Chỉ các đỉnh kề nhau mới được nối với nhau
- Đường gấp khúc không tự cắt
Figure 2: Ví dụ 2 cách nối với N = 6.
Hãy viết chương trình tính số cách nối thỏa mã các điều kiện trên. Chú ý in ra kết quả theo mô đun 1,000,000,000.
Input
Dòng duy nhất chứa số nguyên N (N <= 1,000,000,000).
Output
Gồm một dòng duy nhất là số cách nối theo mô đun 1,000,000,000.
Example
Input: 3 Output: 8
Input: 4 Output: 40
Added by: | sieunhan |
Date: | 2009-05-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Resource: | BOI |