标签:2017 山东一轮集训

2018年6月1日 0 作者 Manchery

LOJ #6077「2017 山东一轮集训 Day7」逆序对

题目链接

还是反序表那套理论,弱化版有 $O(nK)$ 的做法

根据 $\sum x_i=K$ 的容斥计数,需要求得是 $f_{i,j}$ 表示从 $1\sim n$ 中选出 $i$ 个数,和为 $j$ 的方案数

其中 $i$ 的上界 是$O(\sqrt K)$,旋转体积背包 $O(K\sqrt K)$

注意背包时,数字互不相同,且最大的数不能超过 $n$,需要减去一项。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namesp[......]

Read more