Together: Find's Blog

关于群论的一些东西

尽管Pólya是一个很偏的东西, 但还是花了两三天的时间大概的学了一下, 搞了两道sgu上的题. 因为没有系统的学, 所以很多东西还是了解的不透彻.

sgu282 Isomorphism
一道用来实践Pólya原理的好题. 给一个有n个结点的完全图, 求用m种颜色染色的不同方案, 重新排列点的序号后重合的方案算一种.

这道题可以很容易看出需要用Pólya原理, 但是不同的置换方案超过52!(每一种点的置换方案唯一的对应一种边的置换方案). 于是我们需要将点置换分类别, 将置换按循环节长度排序, 如(1)(234)(5678)就是一种”格式”为 1-3-4 置换方案, 如果一种置换表示为 s1-s2-s3-…-sk, 显然 s1+s2+s3+…+sk=n. 于是这是n的一个划分. 通过搜索我们知道53的划分并不多. 当有了一个特定的置换”格式”, 我们可以很容易的用组合数学知识算出有多少种对应的点置换, 对于”格式” s1-s2-s3-…-sk, 有 n!/(s1!*s2!*s3!*…*sk!)/(t1*t2*…*tr) * (s1-1)!*(s2-1)!*(s3-1)!*…*(sk-1)! = n!/(s1*s2*s3*…*sk)/(t1*t2*…*tr) 种, 其中t1, t2, …, tr是相邻重复的sk的个数, 如 1-3-3-4-5-5-5-6 就有 t=(1,2,1,3,1). 由于对Pólya原理的理解不对, 我到这儿以为只要将点置换的个数及循环节数套进公式就可以了, 但这是错的, 回想Pólya原理的证明, 它的证明是建立在Burnside定理基础上的, Burnside定理中对象是不同的染色方案, 染色方案是针对边的, 所以在Pólya原理中置换群中的对象也必须是边 (而不是点).

More »

CEOI 2007 简明解题报告 (不完整)

Day I
Ministry
题目要求计算本质不同的树的形状. 我们可以给每一种不同的树给一个唯一的编号, 那么两棵树相同的充要条件是两棵树的树根有相同数目的孩子且孩子们的编号一一对应. 由于每个结点的孩子数很小(不超过三个), 我们可以从叶子到树根逐一枚举结点, 将三个孩子排个序, 按他们的编号求出一个Hash值, 并找之前有没有出现过相同的结点, 若没有, 则给这个结点分配一个新编号. 最后输出不同编号的个数即可.

Nasty
尽管老师要求计算的值很多, 但是若最后一个数相同, 那么计算结果也将相同, 所以本质不同的x的值只有b个, 预处理一下就可以了.

Sail
提交答案题, 不想做.. 以后再说.
More »

Balkan 2007 简明解题报告

Day I
Cipher
好像应该拿Hash做吧, 标程写的很离奇, 看不懂凭什么可以这么做. 自己也没能写出一个可以AC的程序.

Dream
一道组合数学的题. 分析题目, 实际上是要我们从第一个盒子和最后一个盒子中取一个数, 其他盒子取两个数, 使乘积可以被k整除, 问有多少种方案.
首先求出k的所有因子集合S, 再为盒子中每一个数a在S中找到最大的数b使a mod b = 0. 这两个都需要预处理掉, 还有一个next[a][b]数组, 表示若一个数是k的第a和第b个因子的公倍数, 则它在S中最大的因子是第next[a][b]个因子. 之所以要最大, 在后面的运算中, 方案会优先累计到最大的因子, 即k本身上.
我们用total[a][b]表示到第a行为止, 累计到多少种方案可以使取数之乘积可以被k的被b个因子整除, 需要注意的是, 这里只是累计到的方案, 也就是实际的方案可能比累计到的多, 正如我们之前提到的, 如果某种方案所得到的乘积既能被第a个因子整除, 又能被第b个因子整除, 那么会优先记在记b个因子所表示的total单元中, 即较大的因子头上(假设b>a). 我们先用累加的方法统计第一个盒子中的数字可以被哪个因子整除. 从第二行开始, 先统计单这一行得到的乘积可以被哪个因子整除, 之后再根据乘法原理计到total数组中去. 具体的说, 先用cur1表示只取一个数时可以被哪个因子整除(当然要尽可能大的因子), cur2表示取两个数后乘积可以被哪个因子整除(自然也要尽可能大的因子), cur1用与求第一个盒子相同的方法求出, 再枚举两个因子a,b, 若是相同的因子, 则cur2的next[a][b]单元(即乘积的最大因子)累加cur1[a]*(cur[a]-1) (乘法原理), 若不相同, 则cur2的next[a][b]单元累加cur1[a]*cur1[b]*2 (两种不同的取数顺序). 注意最后一行就不需要这样分两步统计了. 然后再用类似的方法将统计结果累加入total数组中就可以了(再具体的见代码吧).
我的代码写的比较丑, 官方解答写的很漂亮, 看一下就明白了.

More »

准备noi2009时的oj笔记

这是我在准备noi2009时在online judge上的做的部分题目. 从wordpress的修订版本记录来看, 主要记的应该是2008年9月至2009年5月做的题目, 每题都附有简短的算法描述. 另外, usaco曾写过第三章之后几乎全部题解, 但因为Rob认为题解对使用usaco的练习者有害, 所以后来全部删除. 这里曾作为blog的一个页面存在, 现在在online judge上做题没有以前那样的耐心写感受, 即使某天忽然想写专门的题解了, 那也一定是值得我写一篇单独blogpost的收获, 所以这个页面只是留下来做纪念, 不再更新, 发布时间仍保留在2008年.
btw, 我知道自己好没有恒心与毅力, 大家就不用留言鄙视我的题量了.

More »