入れ替え後の点数」が満たされればいい。そのままの点数」を満たせばいい。i番目の数をxと決めると、h[i]=xであればそのままの点数が+1される。h[i+1]=xであれば、入れ替え後の点数が+1される。h[i+1]=xであれば+1となる。よって、i番目の数を決めると-1,0,+1のどれかになる。h[i]==h[i+1]であれば、x=h[i]のときでもx!=h[i]のときでも0になる。どちらでもないとき0。h[i]==h[i+1]であればi番目は何であれ余り関係ないので、その個数をcntとすると、kcnt通りはまずある。h[i]!=h[i+1]の場合がN-cnt個残る。K-2通りで0となる選択肢がN-cnt個あることになる。j)(K-2)N-i-j*kcntの総和が答え。これを後は高速化していく。普通に変形してFFTでもいいんだけど、FPSで高速化することを考える。j)(K-2)N-i-jの総和を求める。cntで以降は考えよう。x)nを計算して、xの自然数乗の係数の総和と等しい。わからないかもしれないが、Easy解法をDPで解くようにすると、ちょうど遷移がこんな感じになる。そのままの点数がpの組み合わせ)x^-1とかは扱いにくいので、(1+(K-2)x+x2)n/(xn)としてしまって、xの自然数乗の係数の総和を足し合わせるのがいい。多項式の積は実際は係数同士でFFTをしている。ある多項式の累乗は、FFT→各要素をN乗→逆FFTで解ける。FFTが理解できていれば、これでそうなることは分かるだろう。TLが1sなので、早いライブラリじゃないとTLEする。なんでDにおいてあるねん」+1と-1は全く対称の操作になるので、同じ組み合わせになる。F]月別アーカイブスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。