No.1310 Quantum Annealing
タグ : / 解いたユーザー数 124
作問者 :
sotanishy
/ テスター :
mugen_1337
renjyaku_int
Problem Statement
$N$ electrons are arranged on a circle. The electrons are numbered clockwise starting from $1$, and the electron following the $N$-th electron is the $1$-st electron.
To each electron, assign a spin $s_i$ of $+1$ or $-1$. There are $2^N$ possible assignments in total. For an assignment, define its energy $E$ by $$ E = -\sum_{i=1}^N s_i s_{i+1} $$ where $s_{N+1} = s_1$.
Compute $2^{|E|}$ for every assignment, and find the sum of these values modulo $998244353$.
Input
$N$
- $N$ is an integer.
- $3 \leq N \leq 2 \times 10^5$
Output
Output the answer.
Sample
Sample 1
Input
3
Output
28
There are 8 spin assignments: $$ (+1,+1,+1),(+1,+1,-1),(+1,-1,+1),(+1,-1,-1), $$ $$ (-1,+1,+1),(-1,+1,-1),(-1,-1,+1),(-1,-1,-1) $$
Computing the energy for each gives $-3, 1, 1, 1, 1, 1, 1, -3$. Therefore, the answer is $$ 2^3 + 2^1 + 2^1 + 2^1 + 2^1 + 2^1 + 2^1 + 2^3 = 28 $$
Sample 2
Input
5
Output
184
Sample 3
Input
15
Output
1854748
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。