yukicoder No.1856 Mex Sum 2
橙diffが解けたので書く！
AとかA'は無視して
mexがiで長さがjの整数列について考える。
dp[i][j]:=mexがiで長さがjの整数列の通り数
この通り数がわかれば
答えは、ΣΣBinomial(n,i)*pow(m+1,n-i)*dp[j][i]*j
になる。なのでdpが求まればいい。
このdpを求める前に
dp0[i][j]:=長さがjで[0,i)で構成されたmexがiの整数列の通り数
を考える。
計算量を無視して、dp0の遷移を考えると
dp0[i+1][j+k]+=dp0[i][j]*Binomial(j+k,k)
Binomial(j+k,k)にjとkが含まれているため扱いにくいが
Binomial(j+k,k)=fact[j+k]*ifact[j]*fact[k]なので
(dp0[i][j]*ifact[j])*fact[k]*fact[j+k]なので
x={dp0[i][0]*ifact[0],dp0[i][1]*ifact[1],dp0[i][2]*ifact[2],,,,,,}
y={fact[0],fact[1],fact[2],fact[3].......}(実際はy[0]=0とする必要がある)
を畳み込んだ
z=convolution(x,y)のi項目に対して、fact[i]をかけたものがdp0になる
これはO(n^2logn)で計算ができる。
dpに戻る。これはdp0から求められる
計算量を無視して、dpの遷移を考えると
dp[i][j+k]+=dp0[i][j]*Binomial(j+k,k)*pow(m-i,j)
なので先ほどと同様に考えると
x={dp0[i][0]*ifact[0],dp0[i][1]*ifact[1],dp0[i][2]*ifact[2],,,,,,}
y={pow(m-0,j)*ifact[0],pow(m-1,j)*ifact[1],pow(m-2,j)*ifact[2],pow(m-3,j)*ifact[3].......}
を畳み込んだ
z=convolution(x,y)のi項目に対して、fact[i]をかけたものがdpになる
これはO(n^2logn)で計算ができる。
よって求まった。
