首先考虑一个 SB 状压 DP:
设 fi,S,j 表示前 i 行,第 i 行放了哲学家的位置的集合为 S,目前放了 j 个哲学家。
这个玩意复杂度是 O(4cnm) 的,其中 c=3。
考虑设 Fi,S(x)=3n∑j=0fi,S,jxj。
那么转移可以写作 Fi,S(x)=∑It is valid to transfer from T to S.x|S|Fi−1,T(x)。
考虑基于 F 的点值表达式进行 DP,设 Fi,k,S 为 Fi,S(ωk3n),那么便可把上述式子写成点值相乘并相加的形式。
然而复杂度还是 O(4cnm) 的,并无卵用(
真的无卵用吗?注意到这样子我们就让 S 这一维的转移相对独立了,并且 S 十分的小,考虑用矩阵乘法优化这一维的转移。
复杂度为 O(8cnlogn)。
(注意多项式的次数界应为 3n,因为我们无法在转移的同时把点值 modxm。)
代码:
1 |
|