Ten Thousand Volts 02 题解

2018-03-27 12:32:03 By Recursion

牛顿的烈焰激光剑

容易得到一个$O(nk)$的dp:$f_{i,j}=f_{i-1,j}+i\times f_{i-1,j-1}$

归纳法易证答案是关于$k$的多项式,拉格朗日插值可以做到$O(n^2)$。

容斥也是可以做的。

另外,倍增可以做到$O(n^2\log k)$,期望得分70分。

眼下,你不需要守在电话铃旁边

显然可以离线,把询问看成二维平面上的点,那么一次修改会对一个矩形内的点有影响。

需要一个支持矩形修改,维护历史最小值标记的数据结构,KD-Tree显然是满足的。

也许有分块的做法,欢迎大家补充。

最终,Alice厌倦了全知全能的Bob

结论:对每个白点,设该子树最大深度为$d$,SG值为$2^{d-1}$。

诸位自证不难。

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。