No.1310 量子アニーリング

• Quiz
  • https://yukicoder.me/problems/no/1310
• AC
  • https://yukicoder.me/submissions/596585
• 解説
  • +1, -1が隣り合う箇所（変化点）に注目する
  • N個のマスに切れ目をいくつか入れ、グループごとに+1, -1を割り当てる。変化点の数は切れ目の数
  • 円環なので切れ目が奇数の場合は変化点がさらに1増える。これで|E|は求まる
  • 切れ目をどこに入れるかもnCrで求まる

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    mint sum=0;
    rep(i,N){
      // i本線を引く
      ll diff;
      ll chigau; // 左右が違う組の数
      ll onaji; // 左右が同じ組の数
      if(i%2==0){
        chigau = i;
      }
      else{
        chigau = i+1;
      }
      onaji = N-chigau;
      diff = abs(chigau-onaji);
      sum += nCr(N-1,i) * mod_pow(2,diff);
    }

    // 最初が1, -1の2パターンある
    sum *= 2;

    p(sum.x);
    
    return 0;
}