問題一覧 > 通常問題

No.1310 量子アニーリング

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 93
作問者 : sotanishysotanishy / テスター : mugen_1337mugen_1337 renjyaku_intrenjyaku_int
20 ProblemId : 5485 / 出題時の順位表
問題文最終更新日: 2020-12-07 09:23:45

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。