传送门 好题。 考察了莫队和组合数学两个知识板块。
首先需要推出单次已知 n , m n,m n,m的答案的式子。 我们令 f [ i ] f[i] f[i]表示当前最大值为第 i i i个数的方案数。 显然 i i i之后的数都是单调递减且连续的。 所以后面的方法是1种。 考虑第 1 1 1~ i − 1 i-1 i−1个位置。 显然放法数为 ∑ j = 1 i − 1 f [ j ] \sum _{j=1} ^{i-1}f[j] ∑j=1i−1f[j] 又因为 f [ 1 ] = 1 , f [ i − 1 ] = ∑ j − 1 i − 2 f [ j ] f[1]=1,f[i-1]=\sum _{j-1} ^{i-2}f[j] f[1]=1,f[i−1]=∑j−1i−2f[j] 因此 f [ i ] = ∑ j = 1 i − 1 f [ j ] = ∑ j = 1 i − 2 f [ j ] + f [ i − 1 ] = 2 ∗ f [ i − 1 ] = 2 i f[i]=\sum _{j=1} ^{i-1}f[j]=\sum _{j=1} ^{i-2}f[j]+f[i-1]=2*f[i-1]=2^i f[i]=∑j=1i−1f[j]=∑j=1i−2f[j]+f[i−1]=2∗f[i−1]=2i 于是此时 A n s = ∑ i = 1 n ( m i ) ∗ 2 i − 1 Ans=\sum _{i=1} ^n \binom {m} {i}*2^{i-1} Ans=∑i=1n(im)∗2i−1 然后考虑在已知当前答案时如何快速求出其它答案。 我们把 n , m n,m n,m看成两个下标 l , r l,r l,r，现在要转移到 l ′ , r ′ l',r' l′,r′。 唉是不是有点莫队的味道。 于是我们只需要考虑如何 O ( 1 ) O(1) O(1)转移。 令 S ( l , r ) = ∑ i = 1 l ( r i ) ∗ 2 i − 1 S(l,r)=\sum _{i=1} ^l \binom {r} {i}*2^{i-1} S(l,r)=∑i=1l(ir)∗2i−1 于是 S ( l + 1 , r ) = S ( l , r ) + ( r l + 1 ) ∗ 2 l S(l+1,r)=S(l,r)+\binom {r} {l+1}*2^l S(l+1,r)=S(l,r)+(l+1r)∗2l
S ( l − 1 , r ) = S ( l , r ) − ( r l ) ∗ 2 l − 1 S(l-1,r)=S(l,r)-\binom {r} {l}*2^{l-1} S(l−1,r)=S(l,r)−(lr)∗2l−1 r的转移可以在杨辉三角上面看。 相当于把一行上下挪动。 推一推发现： S ( l , r + 1 ) = 3 S ( l , r ) + ( r 0 ) ∗ 2 0 − ( r l ) ∗ 2 l S(l,r+1)=3S(l,r)+\binom {r} {0}*2^0-\binom {r} {l}*2^l S(l,r+1)=3S(l,r)+(0r)∗20−(lr)∗2l
S ( l , r − 1 ) = S ( l , r ) + ( r − 1 l ) ∗ 2 l − ( r 0 ) ∗ 2 0 3 S(l,r-1)=\frac {S(l,r)+\binom {r-1} {l}*2^l-\binom {r} {0}*2^0} {3} S(l,r−1)=3S(l,r)+(lr−1)∗2l−(0r)∗20
发现这些东西预处理之后都是可以 O ( 1 ) O(1) O(1)转移的。 于是就可以用莫队了。 代码
