由 $ChitongZ$ 亲自出题.
$game$
考试时候的乱搞:求解最大权重独立子集, $bitset$ 暴力维护线性基.
最坏情况下复杂度为 $O(n^2\log n+\frac {n^3} {64})$ ,但在随机数据下,稍微优化下常数就过了.
正解:记前缀异或和为 $sum$ ,则每次询问区间 $(i,j)$ 相当于是获得了 $sum_{i-1}$ 与 $sum_j$ 的关系.
从 $sum_0$ 到 $sum_n$ 一共有 $n+1$ 个点,而 $sum_0$ 是已知的,所以做出一棵最小生成树就是答案.
$matrix$
模拟退火,先随机出一个状态,每次退火尝试交换两个数,并以一定概率接受较劣的解.
$tree$
考虑暴力 $dp$ ,设 $f(u,i)$ 表示在子树 $u$ 内选出若干点,乘积在模 $m$ 意义下为 $i$ 的方案数.
转移时,枚举 $u$ 的子节点 $v$ ,有 $f’(u,i)=\sum_{j\times k=i} f(u,j)\cdot f(v,k)$ ,然后把 $f’$ 复制到 $f$ 里面.
这样做的时间复杂度是 $O(n\cdot m^2)$ .
转移形式很像卷积,求出 $m$ 的原根 $g$ .
转移就变成了 $f’(u,i)=\sum_{j+ k=i} f(u,j)\cdot f(v,k)$ .
此时 $f(u,i)$ 表示在子树 $u$ 内选出若干点,乘积在模 $m$ 意义下为 $g^i$ 的方案数.
这样就是卷积的形式了,利用 $NTT$ 进行优化,时间复杂度 $O(n\cdot m\log m)$ .