如何把五方优化到线性？
一个长度为 n n n ∑ i r s i − l s i \sum_irs_i-ls_i ∑ i r s i − l s i l s , r s ls,rs l s , r s
求出所有长度为 n n n
n ≤ 10 6 n\le10^6 n ≤ 1 0 6
考虑 d p dp d p
设 f l , r , m f_{l,r,m} f l , r , m [ l , r ] [l,r] [ l , r ] m m m g l , r , m g_{l,r,m} g l , r , m
转移：
f l , r , m ← { ( r − l m − l ) ∑ k 1 = l m − 1 ∑ k 2 = m + 1 r f l , m − 1 , k 1 f m + 1 , r , k 2 m ∈ ( l , r ) ∑ k = l + 1 r f l + 1 , r , k m = l ∑ k = l r − 1 f l , r − 1 , k m = r g l , r , m ← { ( r − l m − l ) ∑ k 1 = l m − 1 ∑ k 2 = m + 1 r ( f l , m − 1 , k 1 g m + 1 , r , k 2 + g l , m − 1 , k 1 f m + 1 , r , k 2 + f l , m − 1 , k 1 f m + 1 , r , k 2 ( k 2 − k 1 ) ) m ∈ ( l , r ) ∑ k = l + 1 r g l + 1 , r , k m = l ∑ k = l r − 1 g l , r − 1 , k m = r \begin{aligned}f_{l,r,m}&\gets \left\{\begin{aligned}&\binom{r-l}{m-l}\sum_{k_1=l}^{m-1}\sum_{k_2=m+1}^{r}f_{l,m-1,k_1}f_{m+1,r,k_2}&&m\in(l,r)\\&\sum_{k=l+1}^rf_{l+1,r,k}&&m=l\\&\sum_{k=l}^{r-1}f_{l,r-1,k}&&m=r\end{aligned}\right.\\g_{l,r,m}&\gets \left\{\begin{aligned}&\binom{r-l}{m-l}\sum_{k_1=l}^{m-1}\sum_{k_2=m+1}^{r}\left(\begin{aligned}&f_{l,m-1,k_1}g_{m+1,r,k_2}
\\+&g_{l,m-1,k_1}f_{m+1,r,k_2}
\\+&f_{l,m-1,k_1}f_{m+1,r,k_2}(k_2-k_1)\end{aligned}\right)&&m\in(l,r)
\\&\sum_{k=l+1}^rg_{l+1,r,k}&&m=l\\&\sum_{k=l}^{r-1}g_{l,r-1,k}&&m=r\end{aligned}\right.\end{aligned} f l , r , m g l , r , m ← ⎩ ⎨ ⎧ ( m − l r − l ) k 1 = l ∑ m − 1 k 2 = m + 1 ∑ r f l , m − 1 , k 1 f m + 1 , r , k 2 k = l + 1 ∑ r f l + 1 , r , k k = l ∑ r − 1 f l , r − 1 , k m ∈ ( l , r ) m = l m = r ← ⎩ ⎨ ⎧ ( m − l r − l ) k 1 = l ∑ m − 1 k 2 = m + 1 ∑ r + + f l , m − 1 , k 1 g m + 1 , r , k 2 g l , m − 1 , k 1 f m + 1 , r , k 2 f l , m − 1 , k 1 f m + 1 , r , k 2 ( k 2 − k 1 ) k = l + 1 ∑ r g l + 1 , r , k k = l ∑ r − 1 g l , r − 1 , k m ∈ ( l , r ) m = l m = r
初始值 f i , i , i = 1 , g i , i , i = 0 f_{i,i,i}=1,g_{i,i,i}=0 f i , i , i = 1 , g i , i , i = 0
五方的。
然后你发现这个区间 d p dp d p f i , m f_{i,m} f i , m i i i m m m
转移式子抄过来：
f i , m ← { ( i − 1 m − 1 ) ∑ k 1 = 1 m − 1 ∑ k 2 = 1 i − m f m − 1 , k 1 f i − m , k 2 m ∈ ( 1 , i ) ∑ k = 1 i − 1 f i − 1 , k m = 1 or m = i g i , m ← { ( i − 1 m − 1 ) ∑ k 1 = 1 m − 1 ∑ k 2 = 1 i − m ( f m − 1 , k 1 g i − m , k 2 + g m − 1 , k 1 f i − m , k 2 + f m − 1 , k 1 f i − m , k 2 ( k 2 − k 1 + m ) ) m ∈ ( 1 , i ) ∑ k = 1 i − 1 g i − 1 , k m = 1 or m = i \begin{aligned}f_{i,m}&\gets \left\{\begin{aligned}&\binom{i-1}{m-1}\sum_{k_1=1}^{m-1}\sum_{k_2=1}^{i-m}f_{m-1,k_1}f_{i-m,k_2}&&m\in(1,i)\\&\sum_{k=1}^{i-1}f_{i-1,k}&&m=1\text{ or }m=i\end{aligned}\right.\\g_{i,m}&\gets \left\{\begin{aligned}&\binom{i-1}{m-1}\sum_{k_1=1}^{m-1}\sum_{k_2=1}^{i-m}\left(\begin{aligned}&f_{m-1,k_1}g_{i-m,k_2}\\+&g_{m-1,k_1}f_{i-m,k_2}\\+&f_{m-1,k_1}f_{i-m,k_2}(k_2-k_1+m)\end{aligned}\right)&&m\in(1,i)\\&\sum_{k=1}^{i-1}g_{i-1,k}&&m=1\text{ or }m=i\end{aligned}\right.\end{aligned}
f i , m g i , m ← ⎩ ⎨ ⎧ ( m − 1 i − 1 ) k 1 = 1 ∑ m − 1 k 2 = 1 ∑ i − m f m − 1 , k 1 f i − m , k 2 k = 1 ∑ i − 1 f i − 1 , k m ∈ ( 1 , i ) m = 1 or m = i ← ⎩ ⎨ ⎧ ( m − 1 i − 1 ) k 1 = 1 ∑ m − 1 k 2 = 1 ∑ i − m + + f m − 1 , k 1 g i − m , k 2 g m − 1 , k 1 f i − m , k 2 f m − 1 , k 1 f i − m , k 2 ( k 2 − k 1 + m ) k = 1 ∑ i − 1 g i − 1 , k m ∈ ( 1 , i ) m = 1 or m = i
然后你发现你记这个 f f f f i , m f_{i,m} f i , m ( i − 1 ) ! (i-1)! ( i − 1 )!
转移式子：
g i , m ← { ( i − 1 m − 1 ) ∑ k 1 = 1 m − 1 ∑ k 2 = 1 i − m ( ( m − 2 ) ! g i − m , k 2 + ( i − m − 1 ) ! g m − 1 , k 1 + ( m − 2 ) ! ( i − m − 1 ) ! ( k 2 − k 1 + m ) ) m ∈ ( 1 , i ) ∑ k = 1 i − 1 g i − 1 , k m = 1 or m = i g_{i,m}\gets \left\{\begin{aligned}&\binom{i-1}{m-1}\sum_{k_1=1}^{m-1}\sum_{k_2=1}^{i-m}\left(\begin{aligned}&(m-2)!&g_{i-m,k_2}&\\+&(i-m-1)!&g_{m-1,k_1}&\\+&(m-2)!(i-m-1)!&(k_2-k_1+m)&\end{aligned}\right)&&m\in(1,i)\\&\sum_{k=1}^{i-1}g_{i-1,k}&&m=1\text{ or }m=i\end{aligned}\right.
g i , m ← ⎩ ⎨ ⎧ ( m − 1 i − 1 ) k 1 = 1 ∑ m − 1 k 2 = 1 ∑ i − m + + ( m − 2 )! ( i − m − 1 )! ( m − 2 )! ( i − m − 1 )! g i − m , k 2 g m − 1 , k 1 ( k 2 − k 1 + m ) k = 1 ∑ i − 1 g i − 1 , k m ∈ ( 1 , i ) m = 1 or m = i
四方的。
然后你发现有一些式子里只有一个 k 1 k_1 k 1 k 2 k_2 k 2
g i , m ← { ( i − 1 m − 1 ) ( ( i − m ) ( i − m − 1 ) ! ∑ k 1 = 1 m − 1 g m − 1 , k 1 + ( m − 1 ) ( m − 2 ) ! ∑ k 2 = 1 i − m g i − m , k 2 + ( m − 2 ) ! ( i − m − 1 ) ! ∑ k 1 = 1 m − 1 ∑ k 2 = 1 i − m ( k 2 − k 1 + m ) ) m ∈ ( 1 , i ) ∑ k = 1 i − 1 g i − 1 , k m = 1 or m = i g_{i,m}\gets \left\{\begin{aligned}&\binom{i-1}{m-1}\left(\begin{aligned}&(i-m)(i-m-1)!\sum_{k_1=1}^{m-1}g_{m-1,k_1}\\+&(m-1)(m-2)!\sum_{k_2=1}^{i-m}g_{i-m,k_2}\\+&(m-2)!(i-m-1)!\sum_{k_1=1}^{m-1}\sum_{k_2=1}^{i-m}(k_2-k_1+m)\end{aligned}\right)&&m\in(1,i)\\&\sum_{k=1}^{i-1}g_{i-1,k}&&m=1\text{ or }m=i\end{aligned}\right.
g i , m ← ⎩ ⎨ ⎧ ( m − 1 i − 1 ) + + ( i − m ) ( i − m − 1 )! k 1 = 1 ∑ m − 1 g m − 1 , k 1 ( m − 1 ) ( m − 2 )! k 2 = 1 ∑ i − m g i − m , k 2 ( m − 2 )! ( i − m − 1 )! k 1 = 1 ∑ m − 1 k 2 = 1 ∑ i − m ( k 2 − k 1 + m ) k = 1 ∑ i − 1 g i − 1 , k m ∈ ( 1 , i ) m = 1 or m = i
阶乘可以化简：
g i , m ← { ( i − 1 m − 1 ) ( ( i − m ) ! ∑ k 1 = 1 m − 1 g m − 1 , k 1 + ( m − 1 ) ! ∑ k 2 = 1 i − m g i − m , k 2 + ( m − 2 ) ! ( i − m − 1 ) ! ∑ k 1 = 1 m − 1 ∑ k 2 = 1 i − m ( k 2 − k 1 + m ) ) m ∈ ( 1 , i ) ∑ k = 1 i − 1 g i − 1 , k m = 1 or m = i g_{i,m}\gets \left\{\begin{aligned}&\binom{i-1}{m-1}\left(\begin{aligned}&(i-m)!\sum_{k_1=1}^{m-1}g_{m-1,k_1}\\+&(m-1)!\sum_{k_2=1}^{i-m}g_{i-m,k_2}\\+&(m-2)!(i-m-1)!\sum_{k_1=1}^{m-1}\sum_{k_2=1}^{i-m}(k_2-k_1+m)\end{aligned}\right)&&m\in(1,i)\\&\sum_{k=1}^{i-1}g_{i-1,k}&&m=1\text{ or }m=i\end{aligned}\right.
g i , m ← ⎩ ⎨ ⎧ ( m − 1 i − 1 ) + + ( i − m )! k 1 = 1 ∑ m − 1 g m − 1 , k 1 ( m − 1 )! k 2 = 1 ∑ i − m g i − m , k 2 ( m − 2 )! ( i − m − 1 )! k 1 = 1 ∑ m − 1 k 2 = 1 ∑ i − m ( k 2 − k 1 + m ) k = 1 ∑ i − 1 g i − 1 , k m ∈ ( 1 , i ) m = 1 or m = i
这个时候你可能会发现我们上面那个式子同时适用于下面的情况了，但那需要定义 ( − 1 ) ! = 0 (-1)!=0 ( − 1 )! = 0 0 0 0
场上卡在这里好久好久好久好久好久好久，直接导致了我在最后一分钟才调出来且取模炸了喜提 10 10 10
你看最后一项连个 g g g
你考虑先算 ∑ k 1 = 1 m − 1 ∑ k 2 = 1 i − m ( k 2 − k 1 + m ) \sum\limits_{k_1=1}^{m-1}\sum\limits_{k_2=1}^{i-m}(k_2-k_1+m) k 1 = 1 ∑ m − 1 k 2 = 1 ∑ i − m ( k 2 − k 1 + m )
这个东西你考虑它的实际意义：左边选一个位置，右边选一个位置，下标的差。
那我们用随机与期望来理解这件事，左边随机一个位置的期望位置是 1 + ( m − 1 ) 2 = m 2 \frac{1+(m-1)}{2}=\frac m 2 2 1 + ( m − 1 ) = 2 m m + 1 + i 2 \frac{m+1+i}{2} 2 m + 1 + i m 2 − m + 1 + i 2 = i + 1 2 \frac m 2-\frac{m+1+i}2=\frac{i+1}{2} 2 m − 2 m + 1 + i = 2 i + 1
然后选择的种类数是 ( m − 1 ) ( i − m ) (m-1)(i-m) ( m − 1 ) ( i − m ) ∑ k 1 = 1 m − 1 ∑ k 2 = 1 i − m ( k 2 − k 1 + m ) = ( m − 1 ) ( i − m ) ( i + 1 ) 2 \sum\limits_{k_1=1}^{m-1}\sum\limits_{k_2=1}^{i-m}(k_2-k_1+m)=\frac{(m-1)(i-m)(i+1)}{2} k 1 = 1 ∑ m − 1 k 2 = 1 ∑ i − m ( k 2 − k 1 + m ) = 2 ( m − 1 ) ( i − m ) ( i + 1 )
代回原式：
g i , m ← { ( i − 1 m − 1 ) ( ( i − m ) ! ∑ k 1 = 1 m − 1 g m − 1 , k 1 + ( m − 1 ) ! ∑ k 2 = 1 i − m g i − m , k 2 + ( m − 2 ) ! ( i − m − 1 ) ! ( m − 1 ) ( i − m ) ( i + 1 ) 2 ) m ∈ ( 1 , i ) ∑ k = 1 i − 1 g i − 1 , k m = 1 or m = i g_{i,m}\gets \left\{\begin{aligned}& \binom{i-1}{m-1}\left(\begin{aligned}&(i-m)!\sum_{k_1=1}^{m-1}g_{m-1,k_1}\\+&(m-1)!\sum_{k_2=1}^{i-m}g_{i-m,k_2}\\+&(m-2)!(i-m-1)!\frac{(m-1)(i-m)(i+1)}{2}\end{aligned}\right)&&m\in(1,i)\\&\sum_{k=1}^{i-1}g_{i-1,k}&&m=1\text{ or }m=i\end{aligned}\right.
g i , m ← ⎩ ⎨ ⎧ ( m − 1 i − 1 ) + + ( i − m )! k 1 = 1 ∑ m − 1 g m − 1 , k 1 ( m − 1 )! k 2 = 1 ∑ i − m g i − m , k 2 ( m − 2 )! ( i − m − 1 )! 2 ( m − 1 ) ( i − m ) ( i + 1 ) k = 1 ∑ i − 1 g i − 1 , k m ∈ ( 1 , i ) m = 1 or m = i
化简：
g i , m ← { ( i − 1 m − 1 ) ( ( i − m ) ! ∑ k 1 = 1 m − 1 g m − 1 , k 1 + ( m − 1 ) ! ∑ k 2 = 1 i − m g i − m , k 2 + ( m − 1 ) ! ( i − m ) ! ( i + 1 ) 2 ) m ∈ ( 1 , i ) ∑ k = 1 i − 1 g i − 1 , k m = 1 or m = i g_{i,m}\gets \left\{\begin{aligned}&\binom{i-1}{m-1}\left(\begin{aligned}&(i-m)!\sum_{k_1=1}^{m-1}g_{m-1,k_1}\\+&(m-1)!\sum_{k_2=1}^{i-m}g_{i-m,k_2}\\+&\frac{(m-1)!(i-m)!(i+1)}{2}\end{aligned}\right)&&m\in(1,i)\\&\sum_{k=1}^{i-1}g_{i-1,k}&&m=1\text{ or }m=i\end{aligned}\right.
g i , m ← ⎩ ⎨ ⎧ ( m − 1 i − 1 ) + + ( i − m )! k 1 = 1 ∑ m − 1 g m − 1 , k 1 ( m − 1 )! k 2 = 1 ∑ i − m g i − m , k 2 2 ( m − 1 )! ( i − m )! ( i + 1 ) k = 1 ∑ i − 1 g i − 1 , k m ∈ ( 1 , i ) m = 1 or m = i
这是三方。
然后你看用到 g g g ∑ m g i , m \sum\limits_mg_{i,m} m ∑ g i , m h i = ∑ m = 1 i g i , m h_i=\sum\limits_{m=1}^ig_{i,m} h i = m = 1 ∑ i g i , m
h i ← 2 h i − 1 + ∑ m = 2 i − 1 ( i − 1 m − 1 ) ( ( i − m ) ! h m − 1 + ( m − 1 ) ! h i − m + ( m − 1 ) ! ( i − m ) ! ( i + 1 ) 2 ) h_i\gets 2h_{i-1}+\sum_{m=2}^{i-1}\binom{i-1}{m-1}\left((i-m)!h_{m-1}+(m-1)!h_{i-m}+\frac{(m-1)!(i-m)!(i+1)}{2}\right)
h i ← 2 h i − 1 + m = 2 ∑ i − 1 ( m − 1 i − 1 ) ( ( i − m )! h m − 1 + ( m − 1 )! h i − m + 2 ( m − 1 )! ( i − m )! ( i + 1 ) )
这是平方。
考虑优化这个平方，看到这么多阶乘先把组合数扬了：
h i ← 2 h i − 1 + ∑ m = 2 i − 1 ( i − 1 ) ! ( m − 1 ) ! ( i − m ) ! ( ( i − m ) ! h m − 1 + ( m − 1 ) ! h i − m + ( m − 1 ) ! ( i − m ) ! ( i + 1 ) 2 ) ← 2 h i − 1 + ( i − 1 ) ! ∑ m = 2 i − 1 ( h m − 1 ( m − 1 ) ! + h i − m ( i − m ) ! + i + 1 2 ) \begin{aligned}h_i&\gets 2h_{i-1}+\sum_{m=2}^{i-1}\frac{(i-1)!}{(m-1)!(i-m)!}\left((i-m)!h_{m-1}+(m-1)!h_{i-m}+\frac{(m-1)!(i-m)!(i+1)}{2}\right)\\&\gets2h_{i-1}+(i-1)!\sum_{m=2}^{i-1}\left(\frac{h_{m-1}}{(m-1)!}+\frac{h_{i-m}}{(i-m)!}+\frac{i+1}{2}\right)\end{aligned}
h i ← 2 h i − 1 + m = 2 ∑ i − 1 ( m − 1 )! ( i − m )! ( i − 1 )! ( ( i − m )! h m − 1 + ( m − 1 )! h i − m + 2 ( m − 1 )! ( i − m )! ( i + 1 ) ) ← 2 h i − 1 + ( i − 1 )! m = 2 ∑ i − 1 ( ( m − 1 )! h m − 1 + ( i − m )! h i − m + 2 i + 1 )
把最后一项与 m m m
h i ← 2 h i − 1 + ( i − 1 ) ! ( i − 2 ) ( i + 1 ) 2 + ( i − 1 ) ! ∑ m = 1 i ( h m − 1 ( m − 1 ) ! + h i − m ( i − m ) ! ) h_i\gets 2h_{i-1}+(i-1)!\frac{(i-2)(i+1)}{2}+(i-1)!\sum_{m=1}^i\left(\frac{h_{m-1}}{(m-1)!}+\frac{h_{i-m}}{(i-m)!}\right)
h i ← 2 h i − 1 + ( i − 1 )! 2 ( i − 2 ) ( i + 1 ) + ( i − 1 )! m = 1 ∑ i ( ( m − 1 )! h m − 1 + ( i − m )! h i − m )
设 p x = ∑ i = 1 x h i i ! p_x=\sum\limits_{i=1}^x\frac{h_i}{i!} p x = i = 1 ∑ x i ! h i
h i ← 2 h i − 1 + ( i − 1 ) ! ( i − 2 ) ( i + 1 ) 2 + 2 p i − 1 ( i − 1 ) ! ← 2 h i − 1 + ( i − 1 ) ! ( ( i − 2 ) ( i + 1 ) 2 + 2 p i − 1 ) \begin{aligned}h_i&\gets 2h_{i-1}+(i-1)!\frac{(i-2)(i+1)}{2}+2p_{i-1}(i-1)!\\&\gets 2h_{i-1}+(i-1)!\left(\frac{(i-2)(i+1)}{2}+2p_{i-1}\right)\end{aligned}
h i ← 2 h i − 1 + ( i − 1 )! 2 ( i − 2 ) ( i + 1 ) + 2 p i − 1 ( i − 1 )! ← 2 h i − 1 + ( i − 1 )! ( 2 ( i − 2 ) ( i + 1 ) + 2 p i − 1 )
线性做法！！！！！！
