https://codeforces.com/contest/1261/problem/D2
解説
「そのままの点数 < 入れ替え後の点数」が満たされればいい。
言い換えると、「0 < 入れ替え後の点数 - そのままの点数」を満たせばいい。
i番目の数をxと決めると、h[i]=xであればそのままの点数が+1される。h[i+1]=xであれば、入れ替え後の点数が+1される。
言い換えで考えると、h[i]=xであれば-1, h[i+1]=xであれば+1となる。
よって、i番目の数を決めると-1,0,+1のどれかになる。
h[i]==h[i+1]であれば、x=h[i]のときでもx!=h[i]のときでも0になる。
h[i]!=h[i+1]であれば、x=h[i]のとき-1, x=h[i+1]のとき+1, どちらでもないとき0。
h[i]==h[i+1]であればi番目は何であれ余り関係ないので、その個数をcntとすると、kcnt通りはまずある。
h[i]!=h[i+1]の場合がN-cnt個残る。
それぞれは独立で考えることができ、場面も統一できるので、
1通りで-1, 1通りで+1, K-2通りで0となる選択肢がN-cnt個あることになる。
これは-1がi個, +1がj個で全探索すると、0<j-iのときのcomb(N, i)comb(N-i, j)(K-2)N-i-j*kcntの総和が答え。
これがEasy解法。
これを後は高速化していく。
普通に変形してFFTでもいいんだけど、FPSで高速化することを考える。
kcnt分は最後にかけるとして、comb(N, i)comb(N-i, j)(K-2)N-i-jの総和を求める。
n -= cntで以降は考えよう。
これは、(x^-1 + K-2 + x)nを計算して、xの自然数乗の係数の総和と等しい。
よくわからないかもしれないが、Easy解法をDPで解くようにすると、ちょうど遷移がこんな感じになる。
（dp[i][p] := i番目までで入れ替え後の点数 - そのままの点数がpの組み合わせ）
x^-1とかは扱いにくいので、
(1+(K-2)x+x2)n/(xn)
としてしまって、xの自然数乗の係数の総和を足し合わせるのがいい。
多項式の積は実際は係数同士でFFTをしている。
ある多項式の累乗は、FFT→各要素をN乗→逆FFTで解ける。
FFTが理解できていれば、これでそうなることは分かるだろう。
TLが1sなので、早いライブラリじゃないとTLEする。
超賢い解法への道筋。つよつよ競プロerのツイ
「+1と-1の数が等しくなる分をひいてから2で割る なんでDにおいてあるねん」
+1と-1は全く対称の操作になるので、同じ組み合わせになる。
なるほどなぁ。
