A. 任凭风浪起，稳坐钓鱼台

其实就是一个优化过的暴力。

首先答案 $x^3$ 显然可以转化为 $3$ 个位同时出现的方案数*权值求和。

当 $k<=20$ ，直接异或 fwt ，然后做一个超集求和运算，$C(k,3)$ 枚举就行了。

这个算法不优秀的原因是只关注三个位同时出现，并不需要像异或 fwt 那样考虑那么多位。

考虑把 $k$ 位分成 $num$ 组，其中每组 $a$ 个位。

每次枚举三个组，然后把这三个组的权值接在一起，做一遍异或 fwt 。

之后做一遍超集求和，$a^3$ 统计一下贡献。

之后再枚举两个组、一个组分别统计跨过若干个组的贡献就好了。

这样的话就把 $2^k$ 和直接暴力的组合数 $C(k,3)$ 均摊了一下，复杂度就能过了。

B. 任凭风浪起，稳坐钓鱼台（续）

是一个想不到的数论。

式子很容易化到 $\sum \limits_{i=1}^{n} \mu(i) ( \sum \limits_{j=1}^{n/i} [gcd(i,j)=1]*\mu(j) )$ 的形式。

然后此时可以发现没法做了，如果枚举 $i$，至少 $O(n)$ 肯定人没了。如果枚举后面的点对贡献，$n^2$ 也没戏。

所以此时题解的处理方法是考虑选择一个阈值 $B$。

首先对于 $i \in [1,B]$ 直接暴力统计一下答案。

然后另外一部分贡献属于 $j \in [1,n/B] \ and \ k \in [1,n/B]$ 的点对 $(j,k)$ 。

枚举点对，然后统计符合条件的 $i$ 有多少个。这个时候发现算重了，所以把重的减掉。

为了方便计算，设 $f(n,a)=\sum \limits_{i=1}^n [gcd(i,a)=1]*\mu(i)$ 。

这个函数对于枚举 $i$ 求 $j,k$ 的时候是适用的。对于枚举了 $j,k$ 求 $i$ 的时候也是适用的。

对于 $f$ 的计算，如果 $a=1$ ，可以直接暴力杜教筛，因为 $n$ 只有根号种取值，所以复杂度没啥问题。

否则考虑首先取 $a=low(a)$ ，然后有一个式子

$$f(n,a)=\sum \limits_{d|a} f(n/d,d)$$

证明大概与与 $[i==1]=\sum \limits_{i|d}\mu(i)$ 类似。

可以考虑 $i$ 的贡献，设 $gcd$ 为 $g$，如果 $g \neq1$ ，那么就被容斥掉了。

如果暴力根号枚举 $a$ 的约数，那么复杂度又升天了。

如果 $n ln(n)$ 预处理出所有的约数，那么常数也升天了。

正确的做法是 $n loglog$ 预处理出质因子，然后枚举集合求出约数。

然后发现当 $n*a$ 比较小的时候，计算次数很多就不划算。所以对这些内容直接进行 dp 处理。

dp 的方法是令 $g_{i,j}=[gcd(i,j)=1]$，这个数组可以直接通过更相减损得出，然后就可以直接搞 dp 数组。

然后常数写丑还是过不了，还得疯狂调参才能AC。

C. 鱼和熊掌不可兼得

利用了排列的一个性质。也就是 $i$ 向 $p_i$ 连边，会形成若干个环。

所以考虑如何求出所有的环边，然后就可以通过交换每个环解决问题了。

首先随机出一个错排来，那么如果交换后 $count$ 有值就意味着出现环边。

之后优秀的做法是分治，仅当区间内存在环边的时候继续递归。

问题是如何分组。题解中构造的方法是，第 $x$ 次操作将 $i+j \equiv x \pmod {n-1}$ 的边 $(i,j)$ 分为一组。

对于 $2i \equiv x \pmod {n-1} $，特别加入边 $(i,n-1)$ 。

这样的话就巧妙构造了一种分组方法，使得每条边都出现了一次且仅一次，问题就解决了。