[uoj#479][NOI2019]机器人

这个题貌似做法很多,不知道为什么很多人都用了下降幂?我想了一个纯组合数学的方法,没有用到多项式。我这个题想了一天多,我发现我对容斥的理解还不够深刻。
我模拟赛的时候直接秒出50分,因为这个题一看就会往笛卡尔树上面去想。我们可以认为两个元素相同时坐标小的那个元素较大,那么建出来的树是确定的。直接然后要dp这个树的话显然区间dp最靠谱。那么$f(l,r,k)$表示区间$\lbrack l,r\rbrack$的元素,组成一棵子树,这棵子树的根的元素为$k$的方案数。
那么转移就是$f(l,r,k)=\displaystyle\sum_{l\le m\le r,abs(2m-l-r)\le 2,A(m)\le k\le B(m)} \displaystyle\sum_{1\le k1 \le k} \displaystyle\sum_{1\le k2<k} f(l,m-1,k1)f(m+1,r,k2)$
对于每一个$\lbrack l,r\rbrack$,m的情况只有常数个,而且我们需要的区间个数比较少(n=300的时候大约只有2000个),所以可以拿到50分。
但是这个东西复杂度和数值有关,我们现在需要想一个复杂度和元素值无关的做法。
首先看特殊情况,所有$A,B$均相同,那么我们可以将元素的种类数相同的方案一起统计,那么直接容斥一下就完了。那么60分到手。
然后来看最后几个点。
这个我想了比较久的时间,一直想不出一个可行的多项式时间复杂度做法。
首先,区间dp不能省,否则状态一定会变成指数级别,然后,我们可以考虑将所有数值拆成O(n)段区间,使得每段区间中所有元素的性质相同(懒得解释了)。不妨称从小到大第i段区间中的元素为i阶元素。
接着可以发现,两个没有关联的块可以分别独立计算贡献,不需要合在一起。所以对于每一个区间,我们只需要记录最高阶的信息即可,其它的直接把贡献乘进去就好了。
那么我们可以设状态$f(l,r,x,y)$为区间$\lbrack l,r\rbrack$,最高阶为x,最高阶不同元素个数为y的除最高阶外的方案数。(转移太烦了不想写了,转移的时候系数可以预处理也可以用组合数弄出来)这是一个$O(n^8)$的dp,加前缀和优化可以到$O(n^6)$,再加个FFT可以到$O(n^5\lg n)$。总之很慢,但是这个可以过$n=50$的点,所以75分到手。
75分代码:

然后我又开始自闭了。后来发现我对容斥的理解不够深刻,我们现在主要复杂度在转移上,就是要记录不同的元素个数,这个我们可以把它容斥掉。我们可以先定一个不同元素个数的上界t,然后假装一共只有这t个数进行dp。那么列出dp方程$g(l,r,x,t,k)$表示…最高阶为x,假装t个元素,此时最大的元素为t个元素中的第k个的方案数。那么转移就变成$O(1)$了,然后容斥系数需要预处理(dp或者组合数都可以)。接着可以发现这个t这一维状态根本不需要,所以这个dp就变成$O(n^4)$了。
现在空间也是$O(n^4)$,可以发现x这一维可以滚动掉,那么空间变成$O(n^3)$了,由于可行状态数少,所以可以过。
卡卡常甚至可以卡进1s。
正常代码(2187ms):

卡常之后的代码(872ms):

Tagged with:

发表评论