LOJ150 - 挑战多项式

这题非常的水,我们拉个板子就 A 掉了 …

前置知识 Polya 定理。

会了以后推一下式子,得

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

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

Polya 定理学习笔记

这个东西其实之前一直想学但是咕咕咕了 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)} $ 。

CF1105E - Helping Hiasat

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

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

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

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

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

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

CF1100F - Ivan and Burgers

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

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

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

洛谷3601 签到题

这题非常的签到。

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

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

洛谷5029 - T'ill It's Over

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

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

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

洛谷4841 - 城市规划

想 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$ 即可。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×