問題一覧 > 通常問題

No.1310 量子アニーリング

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 119
作問者 : sotanishy / テスター : mugen_1337 renjyaku_int
23 ProblemId : 5485 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-12-07 09:23:45

問題文

N個の電子が円周上に並んでいます．電子には時計回りに1から番号がついており，N番目の電子の次は1番目の電子です．

それぞれの電子に+1か−1のスピンsiを当てはめます．当てはめ方は全部で2N通りあります．ある当てはめ方に対して，エネルギーEを E=−∑i=1Nsisi+1 で定義します．ここで，sN+1=s1とします．

すべての当てはめ方に対して2|E|を求め，その合計を998244353で割った余りを求めてください．

入力

N

  • Nは整数
  • 3≤N≤2×105

出力

答えを出力してください．

サンプル

サンプル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となります．よって，答えは 23+21+21+21+21+21+21+23=28 となります．

サンプル2
入力
5
出力
184

サンプル3
入力
15
出力
1854748

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。