传送门
好题。
考察了莫队和组合数学两个知识板块。
首先需要推出单次已知n,mn,mn,m的答案的式子。
我们令f[i]f[i]f[i]表示当前最大值为第iii个数的方案数。
显然iii之后的数都是单调递减且连续的。
所以后面的方法是1种。
考虑第111~i−1i-1i−1个位置。
显然放法数为∑j=1i−1f[j]\sum _{j=1} ^{i-1}f[j]∑j=1i−1f[j]
又因为f[1]=1,f[i−1]=∑j−1i−2f[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=1i−1f[j]=∑j=1i−2f[j]+f[i−1]=2∗f[i−1]=2if[i]=\sum _{j=1} ^{i-1}f[j]=\sum _{j=1} ^{i-2}f[j]+f[i-1]=2*f[i-1]=2^if[i]=∑j=1i−1f[j]=∑j=1i−2f[j]+f[i−1]=2∗f[i−1]=2i
于是此时Ans=∑i=1n(mi)∗2i−1Ans=\sum _{i=1} ^n \binom {m} {i}*2^{i-1}Ans=∑i=1n(im)∗2i−1
然后考虑在已知当前答案时如何快速求出其它答案。
我们把n,mn,mn,m看成两个下标l,rl,rl,r，现在要转移到l′,r′l',r'l′,r′。
唉是不是有点莫队的味道。
于是我们只需要考虑如何O(1)O(1)O(1)转移。
令S(l,r)=∑i=1l(ri)∗2i−1S(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)+(rl+1)∗2lS(l+1,r)=S(l,r)+\binom {r} {l+1}*2^lS(l+1,r)=S(l,r)+(l+1r)∗2l
S(l−1,r)=S(l,r)−(rl)∗2l−1S(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)=3S(l,r)+(r0)∗20−(rl)∗2lS(l,r+1)=3S(l,r)+\binom {r} {0}*2^0-\binom {r} {l}*2^lS(l,r+1)=3S(l,r)+(0r)∗20−(lr)∗2l
S(l,r−1)=S(l,r)+(r−1l)∗2l−(r0)∗203S(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)转移的。
于是就可以用莫队了。
代码