BZOJ 1478 | 1488 | 1815 无标号无向完全有色图计数

给定一个无向完全图,边有颜色,求所有不同构的图的数量。

这里我们考虑所有边的置换,边的置换太大了,发现边的置换和点的置换是有关的,而且点的置换和图的同构是有关的,所以我们枚举所有点的置换。

但是这样是 n! 的复杂度。我们发现对于两个置换,如果对于每一个大小的轮换,他们都具有相同的轮换个数,那么对于答案的贡献就是等价的。

那么我们就可以枚举整数拆分了。复杂度变成点数的拆分数了。

这样我们对于每一置换都求一下对答案的贡献,然后乘一下轮换个数就好了。

轮换个数怎么算呢……首先是根据拆分组合数搞一下

其中 div_num 是拆分数组。

然后考虑假设大小为 x 的轮换有 y 个,那么我们还要除以 y!

然后注意到每个循环排列方式只和第一个点有关,或者说,因为这是个圆排列所以要去重 (除掉 div\_num[i]),所以我们还要挨个乘 (div\_num[i]-1)!

然后后面就是考虑怎么算边的轮换大小了,见这里:

https://fancydreams.ink/2018/12/01/%E4%BB%8E%E5%B0%8F%E5%AD%A6%E5%BC%80%E5%A7%8B%E7%9A%84%E6%95%B0%E6%95%B0/

代码:

 

CQOI2005 三角形面积并

计算几何 × 扫描线入门题

首先把线段都搞出来,然后求所有线段交点的横坐标(包括三角形顶点)并且去重。

也就是求出所有线段交点的 x 轴垂线。

然后把数据排序,枚举相邻的一对垂线,这个时候差不多是这样的

沃日,这图太大了。。 iPad Mini 2 的 Retina 屏真带劲。。

然后你会发现枚举的垂线中间夹着的是若干梯形。假设枚举的是 x_1,x_2 ,那么我用 \frac{(x_1+x_2)}{2}=0 这个“中间的直线”去切割这截出来的一大堆梯形。

显然同一个三角形在 x_1,x_2 之间的部分会被这个直线穿两次,如果我们把下面那次看做一个 ( ,上面的看做 ) ,这就是求所有 至少被一对括号包括起来 的部分的长度。然后用这个长度乘以 x_2-x_1 就是这部分的答案。

还有一点细节是比如像绿色那货,它有条直线是和 x 垂直的,因为特判难写难调,精度要求不高,那条直线直接给他加上一个 OFFSET 带走。比如变成斜率 k=10^{-5} 什么的。

代码。注意精度问题。

 

 

 

 

 

 

 

 

BZOJ2532 | CERC2010 Casting Spells

首先跑马拉车。

然后对于每个位置 i 我们求出他的回文对称半径 r_i 。比如说图上假设 i 是回文子串的中心(如果是偶数长度那就是中心的右侧),然后红色位置是子串的右末端,那么 r_i 就是:

然后有了 r_i 之后我们考虑合法的串长什么样子:

于是我们的任务就是找到满足以下条件的 j

  •  j+r_j \geqslant i
  •  j \geqslant i-\frac{r_i}{2}

然后就可以了。那么这里有一个 O(n \log n) 的搞法:从左到右枚举 i ,并同时维护两个集合:一个是当前所有满足条件 [1] 的 j 的位置集合,这个集合以 r_j+j 排序,并记录每个 r_j+j 对应的 j

另一个集合维护所有当前的合法位置 j ,并按照 j 排序。

每次扫到一个 i 只需先清空位置集合所有 r_j+j < ir_j+j 和合法集合对应的 j

然后求合法集合里 i - \frac{r_i}{2} 的后继即可。

 

BZOJ3895 取石子

这题思路不错。

首先考虑对于一个 >1 的堆,如果合并他对先手有利,那么这堆石子在取完之前一定会被先手合并。同理如果对后手有利也是。

既然合并这个动作要不就是对先手有利要么就是对后手有利,那肯定这堆石子最后会被合并。

并且在取完之前,合并这个动作无论在何时发生,都等同于在对这堆石子操作时的前两步内发生。

那么我们就可以把充裕堆 ( 大小 >1 的堆 ) 先提前合并了,然后在 DAG 游戏图上记搜 \mathrm{SG} 值。

操作分为几种:

  • 拿走一个孤单堆
  • 拿走充裕堆的一个石子
  • 把一个孤单堆合并到充裕堆内
  • 把两个孤单堆合并,成为充裕堆的一部分

然后就写个代码就好了。复杂度大概是 O(T \cdot \sum{a_i}) 的。

 

[HNOI2008] Cards

这应该是最传(麻)统(烦)的做法

首先题目里面有句话说

输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。

这话啥意思?意思就是置换群大小 |G| = m+1 (自己到自己也算一个)

(并且(除幺元置换之外)没有不动点,这个性质直接导致了那个组合数的解法)

上文的大概证明可以找找洛谷上的题解

不过我们还是可以这么做:

找每个置换 g_i 的循环节,然后DP出不动点的个数。

最后算一下方案就好了, 直接硬上 Burnside

 

关于 Purfer 序列

随便抄点什么玩意当笔记用

purfer 序列是啥就不说了

构造方法

不断选取树上编号最小的叶子删除,并加入序列的末尾。

还原方法

\mathbb{A} = \{ 1, 2, 3, \cdots , n \} 以及 purfer 序列 \{ a_i \}

\mathbb{A} 是所谓的度数序列,初始值全是 1 ,然后 Purfer 序列里每个数字都对 \mathbb{A} 1 的贡献。

顺次取出 Purfer  的首个元素,并在 \mathbb{A} 中选择最小的度数为 1 的元素与之连边。

之后这两个元素的度数均 -1

最后 \mathbb{A} 中应该还剩两个元素,将它们连边。

一个性质

因为要进入 purfer 序列就必须要成为一个叶子,那么也就是说 (对于原数的非叶节点) 每个节点在 purfer 序列中出现了它的度数 -1 这么多次 (有一个临点要当父亲) 

(HNOI2008)

从小学开始的数数

Introduction

\sigma 是一个从集合 \mathbb{A}=\{ 1,2,\cdots,n \} 到自身的一一映射 , 那么可以称 \sigma 为置换 ,  形如

\sigma =\left( \begin{matrix} 1& 2& 3& \cdots& n \\ a_1& a_2& a_3& \cdots& a_n \end{matrix} \right)

(其中 \{a_i\} 是一个排列)

P.S. 置换可以做乘法,比如 \left( \begin{array}{c} a \\ b \end{array} \right) \cdot \left( \begin{array}{c} b \\ c \end{array} \right) =\left( \begin{array}{c} a \\ c \end{array} \right)

置换+群论

置换群 ?

置换群 (G,\cdot) (我就直接记作 G 了…) 是一个置换的群. 也即一个带有 (其实严格说叫做装备 equip) 二元运算的置换的集合 , 并满足群的四个性质:

  1. \text{封闭性:\ }\forall a\in G,b\in G,a\cdot b\in G
  2. \text{结合律:\ }\left( a\cdot b \right) \cdot c=a\cdot \left( b\cdot c \right)
  3. \text{幺元}\left( \text{单位元} \right) :\ \exists e\in G,\ \text{s.t}.\forall a\in G,\ e\cdot a=a\cdot e=a
  4. \text{逆元:\ }\forall a\in G,\ \exists b\in G,\ \text{s.t.\ }a\cdot b=b\cdot a=e

(所有的群存在唯一逆元和唯一幺元 , 具体的证明在一个叫做 “OI实用群论” 的文里)

染色问题与等价

定义 在一个群上 , x 为对集合 \mathbb{A} 元素的着色方案 , \mathbb{C} 为所有着色方案的集合 ;

定义 如果 \exists g_i \in G 使得 g_i \cdot x = y , 称作 x,y 等价.

Burnside Lemma

要解决的问题就是在给定置换群 G 和着色方案集合 \mathbb{C} 的情况下, 求出有多少种本质不同的着色方案 (也就是两两不等价).

定义 \mathbb{C}(f) 为在置换 g_i \in G 的作用下不变的染色方案的集合. 集合中的元素(这里的元素是染色方案)又称该置换下的不动点.

N(G,\mathbb{A})= \frac{1}{|G|}\sum_{ g \in G } |\mathbb{C}(g)|

(等价类数目为各集合不动点数目的均值)

Pólya Theorem

G 为对 n 个对象的置换群 , 每个对象可以用 m 种颜色染色 , 等价类数目是 :

N(G,\mathbb{C}) = \frac{1}{|G|} \sum_{ i = 1 }^{|G|} m^{c(g_i)}

其中 c(g_i) g_i \in G 的轮换 (循环节) 的个数 .

(说到轮换 , 突然想到曾经写过一个挺好玩的文)

这就意味着如果染色 x \in \mathbb{C} g_i \in G 的作用下不变 , 那么每个轮换中的元素必须染同种颜色 .

Important conclusions

第一个结论是循环移位的。

通过(循环)移位形成的置换,假设一个 n 个对象的置换,循环移位 k 位,轮换数为 \gcd(n,k)

第二个结论是图上置换群的。

对于 n 个点的无向有色完全图,点的置换有 n 个元素,对于每一个大小设为 a 的轮换,这个轮换对应的完全子图的边的轮换 \frac{a}{2} 个,对于两个大小为 a,b   的轮换,ab 之间的边所形成的置换,它的轮换有 \gcd(a,b) 个。

证明的话 我们先证后面那条,考虑一条边的颜色 c(x,y) 其中 xy 属于不同的轮换 ( 轮换大小分别为 n,m ) ,考虑边的轮换都要同色,这样我们保证的是 \forall k , c(x,y) = c(x+k \mathrm{ mod } n , y+k \mathrm { mod } m)

那么每个点其实都一样了。用类似结论 [1] 的证法可以发现是 \gcd(n,m)

而且你会发现因为一共 ab 条边,所以说每个循环节大小是 \mathrm{lcm}(n,m) 的。

然后前面那条是类似的。。(不负责任)

前面那条的话,一个  好理解的证法是枚举一个点,发现这个点所在的对称轴把轮换这个环分成两半了。然后对于对称的一半,这些点与 1 的边会转会来,然后只需要考虑一半的点就好了-0-

– END –

随便搞搞 ICG (公平组合游戏) 和其余的博弈

写在阅读之前:

本文是我在 10 月份期间开始的对一些见过或者想要学习的博弈模型的一个总结计划。本文篇幅较长,覆盖多种模型,以下是一份可以帮助阅读、理清主干的主题清单:

(待填充)

请注意本文分多页,可以在文末翻页

文章中数学证明、公式较多,请做好阅读理解的准备。这篇文不是闹着玩的,读就请认真读它。先说一句比较自以为是的话:

读这篇文学习博弈论的过程,并不是去背公式或者记性质,而是去熟悉并掌握处理博弈问题的一般思维方式。

快速索引:

Wythoff Game –  第 1 页

Nim Game – 第 2 页

从 Nim Game 到其他组合游戏 ||  归纳与推广、泛化模型 – 第 3 页

SG 函数的构造 || 更进一步的推广 – 第 4 页

Anti-Nim 与 Anti-SG – 第 5 页

Multi-SG || Every-SG – 第 6 页

翻硬币游戏 || NimK || 扩展 NimK第 7 页

树上删边游戏 || 无向图的删边游戏 – 第 8 页

扩展阅读列表  – 第   页

记号约定清单:

对于集合,用 \mathbb{A} 的字体表示。

对于局面,用 \mathbf{a} 的字体或 \mathrm{S},\mathrm{T} 来表示。

\text{s.t.}  → “ 使得 ”  , such that subject to 的缩写。

\forall \exists 分别为 “ 任意 ” 和 “ 存在 ” 的意思(数学量词)。

\oplus  → 代表 xor ( 按位异或 ) 运算。

DAG → 有向无环图。

ICG → 公平组合游戏。

SG → Sprague-Grundy 函数


Wythoff Game

经典的 Wythoff 博弈模型。

这个模型的描述是这样的:地上有两堆石子,其中一堆有 m 个石子,另外一堆有 n 个石子。两名玩家轮流取走石子,规定每次要么从其中一堆石子中取走任意多个石子,要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了,谁就输了。也就是说,取到最后一个石子的玩家获胜。

这玩意其实还可以描述为:

把国际象棋棋子皇后放在棋盘上,两人遵循棋子的走法,轮流移动棋子,但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角,谁就获胜。

描述局面、获得结论

我们知道博弈的关键就是局面,那么我们考虑用一个数学模型去描述局面好了。我们把局面记作一个无序二元组 (n,m)

  • 首先我们知道 (0,0) 是一个必败态
  • 其次, (n,0) \,(n \in \mathbb{N}_{+}) (n,n) \,(n \in \mathbb{N}_{+}) 是必胜态,因为先手拿走 n 就好了。
  • 再然后,我们考虑一个更加一般的状态 A=(n,m) \,( n,m \in \mathbb{N}_{+} \,\, , n \ne m)

我们先给出结论:所有先手必败的数对(我们称为奇异局面)分别是:

(1, 2), (3, 5), (4, 7), (6, 10), (8, 13)

更严格地来说,其实是:

\mathbb{S} = \{(\lfloor 1 \cdot \varphi \rfloor , \lfloor 1 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 2 \cdot \varphi \rfloor , \lfloor 2 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 3 \cdot \varphi \rfloor , \lfloor 3 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 4 \cdot \varphi \rfloor , \lfloor 4 \cdot \varphi^2 \rfloor ) \}

其中的 \varphi \frac{ \sqrt{5}+1 }{2}

关于这个结论最科学的推法(而不是什么打表找规律),这里有我整理的一份文档,可以读一读 : Wythoff Game

证明结论

这里我们尝试证明这些状态的三个性质,从而证明这个构造是先手必败的(设状态为 \forall A \in \mathbb{S} )  :

  • 状态 A 无法一步转移到状态 (0,0)
  • 状态 A 无法一步转移到 \mathbb{S} 的另一个状态。
  • 状态集合 \mathbb{S} 之外的任何非零状态都可以一步转移到一个零状态\mathbb{S} 中的某一状态。

这样我们的博弈策略是后手始终把当前状态转移到 \mathbb{S} 中的状态,从而可以胜利。

对于上面三条性质的证明,可以在这里找到。我有空再仔细补坑

[Codeforces R489D2C] Nastya and a Wardrobe

手模一下发现除掉最后一轮会形成一个区间

那么

L=\left( \left( \left( x\times 2 \right) -1 \right) \times 2-1 \right) \times 2-1\cdots =x\cdot 2^k-2^{k-1}-2^{k-2}\cdots -1 L=x\cdot 2^k-2^k+\text{1 } R=x\cdot 2^k \text{ans}=\frac{S\left( L,R \right) \times 2}{2^k} =\frac{\frac{\left( R-L+1 \right) \left( R+L \right)}{2}\times 2}{2^k} =\frac{2^k\cdot \left( x\cdot 2^{k+1}-2^k+1 \right)}{2^k} =x\cdot 2^{k+1}-2^k+1

然后暴算这个东西。

闲的无聊随便写点| [CQOI2015]任务查询系统

主席树板儿

考虑把添加优先级为 k 的任务转化为在时间 \mathrm{st} 上加 k ,在时间 \mathrm{en}+1 上减 k

那么这样就成功维护了差分咯,然后每棵权值树单独地维护前缀和就行。

注意要离散化和排序。

06/06,应该是一轮集训 (之前) 做的题咯。