No.1310 量子アニーリング
タグ : / 解いたユーザー数 116
作問者 :
sotanishy
/ テスター :
mugen_1337
renjyaku_int
問題文
$N$個の電子が円周上に並んでいます．電子には時計回りに$1$から番号がついており，$N$番目の電子の次は$1$番目の電子です．
それぞれの電子に$+1$か$-1$のスピン$s_i$を当てはめます．当てはめ方は全部で$2^N$通りあります．ある当てはめ方に対して，エネルギー$E$を $$ E = -\sum_{i=1}^N s_i s_{i+1} $$ で定義します．ここで，$s_{N+1} = s_1$とします．
すべての当てはめ方に対して$2^{|E|}$を求め，その合計を$998244353$で割った余りを求めてください．
入力
$N$
- $N$は整数
- $3 \leq N \leq 2 \times 10^5$
出力
答えを出力してください．
サンプル
サンプル1
入力
3
出力
28
スピンの当てはめ方は， $$ (+1,+1,+1),(+1,+1,-1),(+1,-1,+1),(+1,-1,-1), $$ $$ (-1,+1,+1),(-1,+1,-1),(-1,-1,+1),(-1,-1,-1) $$ の8通りあります．
それぞれに対してエネルギーを計算すると，$-3, 1, 1, 1, 1, 1, 1, -3$となります．よって，答えは $$ 2^3 + 2^1 + 2^1 + 2^1 + 2^1 + 2^1 + 2^1 + 2^3 = 28 $$ となります．
サンプル2
入力
5
出力
184
サンプル3
入力
15
出力
1854748
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。