C - Ordinary Beauty 考えたこと n^m通りの長さmの数列について、隣り合う2つの差がdである個数の平均値を求める問題 m-1の時が求まれば、mの時がわかる m-1の状態と無関係に増分が決まるから 期待値DPかと思ったけど直前の状況に依存しないので単なる掛け算でOK 2個の値があった時に、その差がdである場合の数 d=0のときn d<=nのとき2(n-d) 長さmの列にはペアがm-1 d=0のとき (m−1)/n d<=nのとき2(m−1)(n−d)/n2 公式解説OK
