P10707 永恒 题解

· · 题解

此做法复杂度为 $O(n\log^2 n+\log m\log^2\log m)$。 我们可以先想着对于每个 $i\le n$ 求出所有长为 $i$、最大异或和为 $m$ 的序列个数。你可以直接去做 Many Xor Optimization Problems。考虑从第一位开始依次添加数字。每加进一个数就和当前的线性基比较。可能有两种结果。如果没能成功加进线性基。那么这个数就是可以被线性基表示出来的。这样这个数有 $2^s$ 种可能性。$s$ 为当前线性基大小。如果成功加入线性基。那么这种情况的方案数可以后算。因为上一种情况的方案数只和线性基里数的个数有关。而和这些数具体是什么无关。 将序列视为格路。成功加入线性基视为上移。加入失败视为右移。那么加入失败的总方案数。就是 $2^s$。$s$ 为此格路下的面积。显然是 $q-$ 二项式定理的形式。再设最终线性基里有 $l$ 个数。当把一个数插入线性基时。设这个数在线性基里对应的是第 $i$ 位。那么这个数比 $i$ 低的位全是任意的。比 $i$ 高的位里面。在线性基里有数的对应位是它的位是任意的。其他位都是固定的。那么假设线性基里存在的位已确定，构成这个线性基的数就有 $2^{a-l+b}$ 种。$a$ 是线性基内数的位数和。不是构成这个线性基的数的位数和。$b$ 是序列里成功插入线性基各位置对应的线性基位数的逆序对。最后由于异或最大值要等于 $m$。每个不在线性基里的位最终异或值是确定的。所以每个这样的位都会让答案乘上 $\frac{1}{2}$。另外线性基里所有的位。$m$ 也必须有。用分治乘可以对于每个 $l$ 计算出这些加入到了线性基里的数的方案数。然后再用 $q$ 数卷积即可。 然而我们要的是可重集。所以考虑对于每个 $i \le n$ 求出长为 $i$、最大异或和为 $m$ 的不重复序列个数。这东西求出来就可以很容易变成可重集了。设这个序列对应的生成函数为 $f(x)$，前两段算的可重序列对应的生成函数为 $g(x)$。显然有: $$f(e^x-1)=g(x)$$ 故： $$f(x)=g(\ln(x+1))$$ 这其实就是斯特林反演。你好。我不会复合 $\ln(x+1)$。但是现在有人会了。请搜索“多项式复合函数（加强版）”。 但是。 $\log_2m\le60 $。$\log_2m\le60 $。$\log_2m\le60 $。$\log_2m\le60 $。 啊啊啊啊啊啊啊啊——