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 »

我的 TCO 结束了

很久没更新了. 似乎总结比赛的解题报告才有写日志的动力… 每周只在参加一两场比赛, 多了精力顾不过来(orz聪牛, 一天三四场比赛都不在话下), 而且大多不是oi形式的比赛, 解题报告也不及时, 没有以前一定要改对的动力(懒还要找个借口..)

tco安排在每周六半夜, 导致这两周的周末就睡过去了, 昨天如愿以偿的被淘汰. 我按照习惯的不在纸上画好就不动手写代码的oi习惯, 250很精心的想好了才动手, 居然写完就可以submit了, 但分数好像就剩了160+.. 第二题想了一半发现想错了(不该纠缠在几何题上..), 第三题是个网络流的模型, 但是我没法证明正确性, 写完有个样例过不去, 最后在剩2s的时候交上, 并成为了房间里第一个被cha掉的程序(challenge开始不过5s就被cha了, 看来太晚交的话目标过于明显), 我以为要cha某题必须要在那道题上有正分才可以, 看到某900分的错误程序, 遗憾的没去管它, 当它被cha掉后, 发现cha它的人没做第三题, 后悔啊.. 我继续保持了tc比赛从未cha成功过的纪录, 囧..

tco之前做了下usaco三月月赛, 状态极差, 等于没做, 想出算法的某题没写完, 剩下的题也没cheat好, usaco越做越差.

剩下的时间研究关于字符串的东西, 看论文做点题, 套用小鱼的经典句型: “字符串是无底洞”(请了解详情的同学自行yy重音位置及附带手势). 看的头昏脑胀眼睛肿, 感觉树状数组(我想说的是后缀数组)很神奇, 但我更喜欢trie图, 感觉好优美(被DC3搞怕了..), 下周不搞字符串了, 感觉时间不够用.

不能再这样低效下去了, 有没有大牛开导一下我啊..