LOJ 2463 「2018 集训队互测 Day 1」完美的旅行

发布于 2018-06-08  2.7k 次阅读


首先,考虑直接DP,显然我们需要求出两个数组:f[i][j]:走一条路,与出来是i,步数为j的方案数;g[i][j]:走若干条路,与出来是i,步数为j的方案数。

显然f可以直接通过矩阵乘法n^3m做出来,但是这样并不能通过,因此我们考虑使用特征多项式来优化,原理就是我们可以用[0,n-1]次的矩阵的线性组合来表示出n次的,然后对于n+t次的矩阵,我们只需要给等式的右边乘上这个矩阵就好了。对于这道题,如果我们枚举了一个与出来的值i,那么我们可以搞出来一个行(列)向量以及它的转置,然后给等式左边和右边乘上这个向量及转置,之后就有递推式了,形式化一点,设\(B_{n+i} = X  A^{n+i} X^{T}\),那么有\(B_{n+i}=\sum _{j=0}^{n-1}h_{j}X A^{j+i} X^{T} = \sum _{j=0} ^{n-1} h_{j} B{j+i} \),之后,我们可以暴力O(n^4)算出前n个矩阵,然后O(n^2m)递推剩下的。

对于特征多项式的求解,由于这道题并不是什么常系数递推,我们只能暴力求解,具体就是用定义式\(char(A) = | A - \lambda E | \),带入不同的λ,求解行列式的值,然后高斯消元得到系数h,复杂度O(n^4+n^3)。

之后我们就能求出f了,考虑如何求g。我们可以先对第一维进行FWT,之后对第二维进行NTT,这样单次卷积的复杂度就是O(nm)了,考虑到最后的结果其实就是k次卷积之和,我们可以用等比数列求和公式转化到多项式求逆上,然后可以O(nmlogm)的复杂度得到结果。考试的时候想的是用倍增来做,不过这样需要每次都DFT回去进行取模,复杂度好像是两个log的。

然后我们只需要卡卡常数就可以过去了,对于32位的机子,只有在卡取模的常数的时候才要用long long,其他的还是全程int吧。多项式取模现算长度应该会快一点?

总的来说,考试的时候只会\(O(n^3 m + n m log^2 m logn)\)的做法,但是觉得前面的n^3m会让这个算法直接沦为最弱的暴力,于是就直接写了\(O(n^3 m + n^2 m^2)\)的,成功被subtask卡掉了。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974