前置知识 Polya 定理。

会了以后推一下式子，得

$$
\begin{aligned}
ans &= \sum_{i=1}^n n^{\gcd(i, n)} \\
&= \sum_{d|n} n^d \varphi(\frac nd)
\end{aligned}
$$

直接做即可。没错我就是来水题解的。

这个东西其实之前一直想学但是咕咕咕了 233.

Burnside 引理

$ans = { 1 \over |G| } \sum_{f \in G} C(f)$ ，其中 $C(f)$ 表示置换 $f$ 中不动点的个数

Polya 定理

定义 $L(f)$ 为置换 $f$ 的循环节数，可以理解为对于任意一种状态至多经过 $L(f)$ 次置换 $f$ 可以变回原样。

易证置换 $f$ 的不动点一定满足其自身的循环节为 $L(f)$ ，即 $C(f) = k^{L(f)}$ ，其中 $k$ 表示颜色种数。

Polya 定理的公式即 $ans = { 1 \over |G| } \sum_{f \in G} k^{L(f)} $ 。

memset0 给自己的博客引入了一言功能 qaq。

有些时候刷出一些好的一言会在这里记录下来。

可以发现，在两个 1 操作之间的人中最多满足一个。我们可以两两连边，这样问题就转换为最大独立集问题，按照套路此时我们作补图，将最大独立集转换为求补图最大团。

最大团的常用算法是 Bron Kerbosch ，我们甚至不需要很强的优化剪枝就可以过掉这题。

最近在别人的 Oneindex 下东西，懒得一个一个点于是就写了个脚本准备一次性下。

成品：github.com/memset0/oneindex-folder-spider

原理其实是很简单的，对于当前这个页面遍历每一个连接：如果是文件就下载，如果是文件夹就递归即可。
下载出来的文件树会和 Oneindex 上的一样。

如果使用的话需要安装 Python3 & requests & wget 。

一道线性基傻逼题。然而我一开始智商掉线连写了两个假算法。

首先这题三只 $\log$ 肯定是过不去的，除非你是 wys；
然后也不能用多个线性基来更新一个答案。

上面都是废话，直接整体二分就过了。

这题非常的签到。

考虑到一个数只能被小于根号的质数筛到，暴力做即可。

复杂度为 $O(n \log n)$ ，其中 $n = r - l + 1$ 。

做那么多水题，会不会被婊…

还是网络流，只不过这次我们需要从一个区间连到另一个区间，那么就是个典型的线段树优化建边。
需要注意一些小细节。

网络流裸题，没什么好说的。
需要注意的是，我们在给厨师拆点的时候，如果先把边都连好，时间是会炸掉的。所以我们就没“用掉”一个厨师新建一次点即可。

想 LJC00118 NOIP 考前就秒切了这题，memset0 又又又被吊打.jpg。

考虑有标号无向图的生成函数：$f(x) = \sum\limits_{i=0}^{\infty} 2^{n \choose i} \frac{x^n}{n!} $。

考虑有标号无向联通图的生成函数 $g(x)$ ，容易证明 $exp(g(x)) = f(x)$ 。

此题需求 $g(x)$ ，那么直接多项式 $\ln$ 即可。