# B - Reversi (opens new window)

# 概要

  • NN個が色CiC_iで塗られている
  • 以下の操作を0回以上の任意の回数行う
    • 同じ色で塗られている2つの石を選ぶ
    • それらの石の間に置かれている石を全て同じ色にする
  • 最終的な石の色としてありうるものの個数を109+710^{9} + 7で割った余りを求めよ

# 思考

  • 実験する
  • 両端が同じ色の時に全て同じ色になる
  • 同じ色が何セット組めるかを考えれば良いのでは?
  • カウントして, N×(N1)÷2N \times (N-1) \div 2した結果を加算していけば良い
    • 片方の端を選ぶのにNN通り, もう片方を選ぶのにN1N-1通り, 両端を逆にしても良いのでN(N1)/2N(N-1)/2通り
  • 最後のサンプルが通らない

30分終了

  • editorialを見る
  • DPらしい

# 気づいたこと・感想

  • AtCoderでもこの構文は使えない......
    • cout << " "[i==0] << ans[i];という表現
  • ちなみにこの構文はアルメリアさんの記事 (opens new window)で見かけたもの
  • 構文の意味を知らないので明日本人に聞いてみる
Last Updated: 1年前