No.579 Size of Cycles on a 3 x N Grid (hard)
タグ : / 解いたユーザー数 20
作問者 :
はむこ
Problem Statement
The undirected graph whose vertices are connected in a lattice pattern, with 4 vertices vertically and $N+1$ vertices horizontally,
is called the $3\times N$ grid. Find the total number of "ways to choose an arbitrary vertex from the $3\times N$ grid and then choose a simple cycle containing that vertex", modulo $10^9+7$.
Input
N
$1\le N \le 10^{18}$
Output
Output the answer on one line. End the output with a newline.
Sample
Sample 1
Input
1
Output
32
There are 8 ways to choose a vertex. If one of the top 2 or bottom 2 vertices is chosen, there are 3 simple cycles containing that vertex. If one of the 4 vertices in the second and third rows from the top is chosen, there are 5 simple cycles containing that vertex. 4 x 3 + 4 x 5 = 32 is the answer.
For $N=2,\dotsc,10$, the answers are 316, 2292, 14422, 84744, 479004, 2638328, 14258574, 75940592, 399782668.
Sample 2
Input
20
Output
424899366
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。