ABC046-B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer を解く

ABC046-B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer

なんだか数学的な問題が来た

難しそうだが、とりあえず具体的な数字で考えてみることにする

たとえば、10個のボールを3色で塗り分ける場合

左端から塗っていくことを考えると、最初の1個目は何色で塗っても問題ない

よって3通り

左から2番目は、左隣の色と被らないようにするため2通りの塗り方がある

左から3番目は、左隣の色と被らないようにするため2通りの塗り方がある

左から4番目は、左隣の色と被らないようにするため2通りの塗り方がある

…

というわけで、10個のボールを3色で塗り分ける場合は

3 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 1536 通り

となる

一般化すると、N個のボールをK色で塗り分ける場合、そのパターン数は

K × (K-1) × (K-1) × … × (K-1) 通り

となる（K-1 は N-1 回 掛ける）

よって、コードは以下のようになる

提出したコード

# 入力
N,K=map(int,input().split())

# 出力
print(K*pow(K-1,N-1))

提出結果はACでした