Burnside引理与Polya计数公式

Burnside引理

设\(A\)和\(B\)为有限集合,\(X\)表示所有从\(A\)到\(B\)的映射集合(着色方案集合)。\(X/G\)表示\(X\)所有元素的轨道的集合(去掉重复),即\(G\)作用在\(X\)上产生的所有等价类的集合,\(X^{g}\)表示\(X\)中在\(g\)作用下的不动元素,则有

\(|X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|\)

\(X\)中非等价的着色数等于在\(G\)中的置换作用下保持不变的着色的平均数!

Polya计数公式

考虑置换\(g\)可以分解成若干不相交的循环置换的乘积,那么每个循环内的颜色必须相同,才能在\(g\)的作用下染色不变,设颜色一共\(m\)种,置换\(g\)的循环分解中的循环个数为\(c(g)\),那么在\(g\)作用下着色不变的着色数为:

\(|X^{g}|=m^{c(g)}\)

替换一下,就得到了:

\(|X/G|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}\)

 

咕咕咕

转眼暑假就要过去,马上开学了,今年这个时间点格外的忙,本来这两月计划的总结也只能咕了,真棒!

数论初级魔法大赏

最近在准备关于莫比乌斯反演的课件,准备把例题简要整理下来,那就开始吧

1.bzoj 2190 [SDOI2008]仪仗队

求\(2+\sum_{x=1}^{n-1}\sum_{y=1}^{n-1}[gcd(x,y)==1](n\le 40000)\)

最简单的做法,线性筛预处理出欧拉函数的前缀和,时间复杂度\(O(n)\)。

2.bzoj 2818 Gcd

求\(\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{n}[gcd(x,y)==p] (n\le 10^7)\)

其实就是\(\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{n}{p}\rfloor}[gcd(x,y)==1]\),枚举所有质数后就是和上一道题一样做法了,双倍经验。

3.bzoj 2705 [SDOI2012]Longge的问题

求\(\sum_{i=1}^{n}gcd(i,n), n\le 2^{32}\)

变形一下,枚举每种gcd的值,即

\(\sum_{i=1}^{n}gcd(i,n)\)

\(=\sum_{d\mid n}d \sum_{x=1}^{\frac{n}{d}}[gcd(x,\frac{n}{d})==1]\)

\(=\sum_{d\mid n}d\varphi(\frac{n}{d})\)

那么根号枚举约数,单点求欧拉函数就做完了。

时间复杂度?是个经典的东西\(O(\sum_{i=1}^{\sqrt{n}}\sqrt{i}+\sqrt{\frac{n}{i}})=O(n^{\frac{3}{4}})\)

4.bzoj 2440 [中山市选2011]完全平方数

求第\(k(k\le 10^9)\)个不含完全平方数因子的正整数

二分答案,转为求前\(n\)个数中有多少数不含完全平方因子。容斥一下,总数减去是4(2的平方)的倍数的,减去9的倍数,16的倍数不用管,前面减过了,再减去25的倍数,加上36的倍数,因为前面多减了一次…那这样就发现了容斥系数就是莫比乌斯函数。时间复杂度\(O(\sqrt{n}\log{n})\)

5.luogu P2257 YY的GCD(bzoj 2820)

求\(\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==p] (n\le 10^7)\),\(T(\le 10000)\)组询问

bzoj 2818的加强版,把其中一个n换成了m,这样就不能用欧拉函数了,推导一下:

下述的\(p\)表示质数

\(\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==p]\)

\(=\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}[gcd(x,y)==1]\)

\(=\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d\mid gcd(x,y)}\mu(d)\)

\(=\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d\mid x \land d\mid y}\mu(d)\)

\(=\sum_{p}\sum_{d=1}^{\lfloor \frac{min(n,m)}{p}\rfloor}\mu(d)\lfloor \frac{n}{pd}\rfloor\lfloor \frac{m}{pd}\rfloor\)

\(=\sum_{k=1}^{min(n,m)}\sum_{p,p\mid k}\mu(\frac{k}{p})\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor\)

\(=\sum_{k=1}^{min(n,m)}f(k)\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor\)

其中第三行莫比乌斯反演,第五行交换求和,第六行令\(k=pd\),转而枚举\(k\),化简到最后用筛法预处理出所有\(f\)的值即可,这里应该可以用线性筛,不过懒得推导的话也可以枚举所有质数再枚举它的倍数这样求,那么时间复杂度就和埃氏筛一样了,之后每次求一组询问就是经典的数论分块了。时间复杂度\(O(n\log{\log{n}}+T\sqrt{n})\)。

6.spoj LCMSUM

求\(\sum_{i=1}^{n}lcm(i,n), n\le 10^{6}\),\(T(\le 300000)\)组询问。

\(\sum_{i=1}^{n}lcm(i,n)\)

\(=\sum_{i=1}^{n}\frac{i\times n}{gcd(i,n)}\)

\(=\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^{2}}{gcd(i,n)}+n\)

\(=\frac{1}{2}\sum_{d\mid n,d\ne n}\frac{n^2}{d}\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor}[gcd(k,\frac{n}{d})==1]+n\)

\(=\frac{1}{2}n\sum_{d\mid n,d\ne n}\frac{n}{d}\varphi(\frac{n}{d})+n\)

\(=\frac{1}{2}n\sum_{d\mid n,d\ne 1}d\varphi(d)+n\)

\(=\frac{1}{2}nf(n)+n\)

这样线性筛预处理完,\(O(n\log{n})\)的求出函数值\(f\),每次回答\(O(1)\)即可。

7.bzoj 2154 Crash的数字表格

求\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j),n,m\le 10^7\)

\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)\)

\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}\)

\(=\sum_{d=1}^{min(n,m)}\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{d}\rfloor}dxy[gcd(x,y)==1]\)

\(=\sum_{d=1}^{min(n,m)}d\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{d}\rfloor}xy\sum_{k\mid x \land k\mid y}\mu(k)\)

\(=\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\lfloor \frac{m}{d}\rfloor}\mu(k)\sum_{x=1}^{\lfloor \frac{n}{dk}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{dk}\rfloor}k^{2}xy\)

\(=\sum_{T=1}^{min(n,m)}\sum_{k\mid T}kT\mu(k)g(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)\)

\(=\sum_{T=1}^{min(n,m)}Tg(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)\sum_{k\mid T}k\mu(k)\)

\(=\sum_{T=1}^{min(n,m)}Tg(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)f(T)\)

 

其中\(g(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij=\frac{n(n+1)}{2}\frac{m(m+1)}{2}\)

一开始头铁,\(O(n\log{n})\)求的\(f(T)\)的值,超时无疑,然后学习了用线性筛求积性函数\(f(T)=\sum_{k\mid T}k\mu(k)\)的思路。

线性筛过程分两种情况讨论

1.\(prime_j\)整除\(i\),那么枚举\(i*prime_j\)的约数\(k\)时,如果关于\(prime_j\)的指数大于等于2的话莫比乌斯函数为零,对答案没有贡献,所以此时\(f(i*prime_j)=f(i)\)。

2.\(prime_j\)不整除\(i\),那么再分枚举的约数\(k\)是否含有\(prime_j\),不含有的部分就是\(f(i)\),含\(prime_j\)的话,整体乘上这么多,并且莫比乌斯函数要变号,是\(-f(i)prime_j\)。综上,此时\(f(i*prime_j)=(1-prime_j)f(i)\)。

这样这道题就做完了,时间复杂度\(O(n)\)。

8.bzoj 3994 [SDOI2015]约数个数和

求\(\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij), n,m\le 50000\),\(T(\le 50000)\)组询问,其中\(d\)是约数个数函数。

这个题一开始卡在一个结论上了,首先要知道\(d(ij)=\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)==1]\),这个结论不好想,但可以用分解质因数的形式结合约数个数定理推出来,那解决了第一步,后面的就简单了。

\(\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)\)

\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)==1]\)

\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid  gcd(x,y)}\mu(k)\)

\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid x \land k\mid y}\mu(k)\)

\(=\sum_{k=1}^{min(n,m)}\mu(k)\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{yk}\rfloor\)

\(=\sum_{k=1}^{min(n,m)}\mu(k)\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor f(\lfloor\frac{m}{k}\rfloor)\)

\(=\sum_{k=1}^{min(n,m)}\mu(k)f(\lfloor\frac{n}{k}\rfloor) f(\lfloor\frac{m}{k}\rfloor)\)

至此又可以数论分块搞定单组询问了,时间复杂度\(O(T\sqrt{n})\)。

9.bzoj 4659 lcm

化简下题意就是求\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)[\mu^2(gcd(i,j))==1],n,m\le 4000000\),对\(2^{30}\)取模,\(T(\le 2000)\)组询问。发现就是在第七题的基础上加了个多组询问,且只统计\(\mu^2(gcd(i,j))==1\)的。

那么前面的推导都是一样的,最后化简到

原式\(=\sum_{T=1}^{min(n,m)}g(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)T\sum_{k\mid T}k\mu(k)\mu^2(\frac{T}{k})\)

头铁依然会TLE,还是先观察一下

\(f(T)=\sum_{k\mid T}k\mu(k)\mu^2(\frac{T}{k})\)是积性函数

且当\(T\)分解质因数后的指数中有大于2的情况的话,显然此时\(f(T)=0\),并且易知\(f(p)=1-p,f(p^2)=-p\),这样又可以线性筛搞一搞了,然后预处理出\(if(i)\)的前缀和。

10.bzoj 4816 [Sdoi2017]数字表格

求\(\prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j)),n,m\le 10^6\),其中\(f\)为斐波那契数列,结果模\(10^9+7\),\(T(\le 1000)\)组询问。

\(\prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j))\)

\(=\prod_{d=1}^{min(n,m)}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)==1]}\)

\(=\prod_{d=1}^{min(n,m)}f(d)^{\sum_{k=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor}\)

这样指数部分是关于\(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor\)的函数,可以分块,又因为外层是枚举的\(d\),所以分块套分块即可!时间复杂度\(O(T(n^{\frac{3}{4}}+\sqrt{n}\log{n}))\),前一部分来源分析同第三题

 

枚举算法再放送

再 放 送

4月24日的时候我讲了程序设计与算法实践的第一课,内容包括算法时间复杂度的概念,枚举与递归等。其中关于枚举这方面还是比较有意思的,从易到难总结了三道题目枚举题,其他的内容就是老生常谈了。实际上枚举算法看似简单又不能很轻易掌握,因为枚举也是有技巧与策略的。在一道具体的题目中,暴力的枚举很可能行不通,但是聪明的枚举往往能起到“四两拨千斤”的效果。

练习题目

1.素数判定

定义一个数是素数当且仅当它是一个大于1的自然数,且不含有除1和它本身以外的因数。

  • 虚假的枚举

直接枚举2到n-1的所有数,看是否能整除n,时间复杂度\(O(n)\)。

  • 真正的枚举

考虑到如果\(n\)是合数,那么就能写成\(n=a\times b(1<a,b<n)\)的形式。

不妨设\(a\le b\)

那么就有\(n=a\times b\ge a^2\)

即\(a\le \sqrt{n}\)

也就是说如果\(n\)是合数,那么就一定有一个根号范围内的因数,所以枚举上界一下子就降下来了,时间复杂度\(O(\sqrt{n})\)。

2.Squarefree number

(题目在bnuoj上也有http://www.bnuoj.com/problem_show.php?pid=7931

给出一个数\(n(1\le n \le 10^{18})\) ,判断n的因数中有没有平方数。比如18有,21没有。

  • 虚假的枚举

直观上来看,需要枚举根号范围内的正整数\(x\),判断\(n\)是否是\(x^2\)的倍数,时间复杂度\(O(\sqrt{n})\)。

  • 真正的枚举

如果\(n\)满足条件,则一定可以表示成\(n=ab^2(b\ne 1)\)的形式。

显然\(a,b\)不同时大于\(10^6\)。

那么我们只需要分别枚举判断即可,其中枚举\(a\)时需要看除完后是否是完全平方数,这个随便搞搞就好了,总的时间复杂度\(O(n^{\frac{1}{3}})\)。

很久之前写的代码了,还是不建议直接用sqrt开方(精度误差),可以开完之后比如在加减5的范围内再for一下找找:

 

3.Forever Young

题目来源是2016 ACM-ICPC World Finals(近几年我校唯一没进总决赛的一次),当时算是第三、四道简单签到题,不过这个签到就非常有水平了。

给一个十进制数\(n(10\le y\le 10^{18})\),和一个下届\(L(10\le L)\),找到最大的正整数\(B\),使得\(n\)在\(B\)进制下只有0到9的数字,并且再当成十进制翻译后,要至少为\(L\)。

题意比较绕,还是需要结合样例理解一下。

  • 虚假的枚举

直接从大到小枚举进制\(B\),然后进制转换,验证是否符合条件,找到就退出,然而光是枚举就需要\(O(n)\),显然不行。

最简单的例子,比如不管\(n\)多大,只要下届是\(10\),答案就可以是\(n\)进制。

  • 真正的枚举

观察到一个数由更大的进制表示时,位数是越来越短的。具体来说

比如\(n=a_0+a_1B+a_2B^2+a_3B^3+\dots\)

发现当\(B>10^6\)时,\(B^3>10^{18}\),也就是说当枚举到\(B>10^6\)时,表示出来的长度不会超过3位。又因为每一位必须是0到9的数字(不能有ABCDEF这样的),那么我直接一个三层循环枚举表示后的结果,最后解一个关于B的一元二次方程\(n=a_0+a_1B+a_2B^2\)就非常trivial了。

最后把这两种枚举方式得到的答案取最大值即可,总的时间复杂度\(O(n^{\frac{1}{3}})\)。

代码写的稍微有点难看,训练的时候以为中间爆long long了,实际是别的地方的问题:

 

怀念金庸

今天是金庸诞辰95周年。想起来2018年10月30日的上午,又或许是前一天晚上,我突发兴致,决定把天龙八部再读一遍,当时还在想不知金庸先生现况如何。

然而晚上即闻金大侠仙逝的噩耗…

世事无常啊,当晚真的为此难受了很久。

过去四个月,我先后读了《天龙八部》、《射雕英雄传》、《神雕侠侣》、《倚天屠龙记》、《笑傲江湖》,深感收获良多。于是我把读书时的所思所想写到了哲学入门课程的期末论文里。文章结合哲学导论课本的一些观点将我目前读到的金庸串连了起来。除了“大闹一场,悄然离去”那一段是参考网上文章以外,其余都是我的原创想法。笔者认为其中一些片段语言可能会稍显尴尬(类似高中作文的那种尬?),不过还是有很多精彩部分的,下面是原文。


从金庸武侠角度浅谈人的哲学

摘要:2018年10月30日,金庸先生在香港逝世,享年94岁。金庸,本名查良镛,当代武侠小说作家、新闻学家、企业家、政治评论家、社会活动家。他的作品曾被誉为“有华人的地方就有金庸的读者”。金庸十余部武侠作品之所以有如此巨大的魅力,和其中蕴含的中华传统文化精华以及处处可见的哲学智慧是分不开的。本文通过简要分析金庸武侠(以《天龙八部》为主)和回顾金庸生平来浅谈人的本质及人生意义等人学话题。

关键词:金庸;武侠小说;人生哲学

一 人性与人的本质

人学最为核心的问题就是关于人是什么的问题。对于这个问题的回答可分为三个层面:一是人的天性是什么?二是人与万物尤其是动物相区别的特性是什么?三是人之为人的内在根据是什么?本节将从金庸武侠中是探讨、回答这三个问题。

(一)金庸武侠中的善恶观

在当代文学作品中人物形象大多刻板:好人就是好人,坏人就是坏人。然而金庸武侠大多不是,至少《天龙八部》一定不是。即使是为万人敬仰的好人也有可能在某些场合做出极不光彩的错事,比如玄慈方丈,听信奸人妄言,埋伏攻击萧远山一家,后来又动了凡心,与叶二娘有私情,由此酿成种种悲剧。即使是万恶不赦的坏人也有可能践行侠义精神,做出大有风度之事。作为四大恶人之首的恶贯满盈段延庆,在将被蛊惑自尽之时,被虚竹救下,遂知恩图报,帮助虚竹破解珍珑棋局。

那么人的天性到底是善是恶?笔者认为,用性无善无恶论的观点更好解释。没有天生的恶人,没有天生的善人。善恶是非都是后天因素造成的,尤其是教育因素。若是从小受佛门经典熏陶,长大必然宅心仁厚。若是误入歧途,卷入恩怨纷争,难免性格乖戾,沦为恶人。而且善恶不过是相对的概念,是可以互相转化的,只要善于引导,人性都有发展向善的可能。武侠小说中弃暗投明或是由正转邪的例子大有人在。

(二)阿朱就是阿朱

人和动物的共同点在于都有自然属性。“所谓人的自然属性,指的是人的生理构造和自然本能方面的属性。”真正区别人与动物的是人的精神属性。“所谓人的精神属性是指人是有意识的存在物,是有精神需要、精神能力以及精神生活的存在物,表现在人具有自我意识,能思维,有理性,具有情感、意志等非理性因素。”

《天龙八部》中有一段耐人寻味的话:“阿朱就是阿朱,四海列国,千秋万载,就只一个阿朱。”无论是空间上还是时间上,阿朱是独一无二的,不能被任何人代替。笔者认为,人的独特在于人具有的自由精神。这种自由精神、自由意识的不同造成了人的性格、情感、认知的不同。“人非草木,孰能无情”是以情感的角度论证人的精神属性。再以精神需要为例,人的自我实现、自我超越的需要是可以抑制基本的生理需要的,这也是马斯洛需求层次理论不足的地方。萧峰因误杀阿朱,愧疚难当,决定此生终不再娶,这里即是精神需要战胜生理需要的例子。

(三)人就是江湖

由前面的观点,自我意识、自由精神固然重要,但还不能简单归为人的本质。关于人的本质,或者说人的内在根据还需要更多探讨。

人除了自然属性与精神属性,更根本的还有社会属性。荀子提出人与动物的差别在于,“人能群,彼不能群也。人何以能群?曰分。”

关于何为江湖,在后来翻拍的《笑傲江湖》中有一句经典台词:“只要有人的地方就有恩怨,有恩怨就会有江湖,人就是江湖。”与其说是江湖的本质,更不如说是直接道出了人的本质。这与马克思所说的“人是一切社会关系的总和”有异曲同工之妙。当然,“在马克思看来,人根本就没有固定不变的本质”。只不过在虚构的武侠世界中,江湖由人构成,恩怨因人而生,说人就是恩怨江湖再贴切不过。

二 人生的意义

(一)红颜弹指老,刹那芳华

金庸笔下的天山童姥可谓是奇异至极,短短几日时间,身体便由青春年少变得垂垂老矣,最终和仇人李秋水激斗后得知她们一生纠缠痴爱的男人另有所爱,于是“同一笑,到头万事俱空”,便双双撒手人寰。正所谓“人生如梦幻泡影,如露亦如电”。当我们突然发觉,弹指一挥间,青丝沾染白雪,自己已经老去,这个时候该如何追忆评价自己的一生?人生到底有无意义?我们是否实现了人生的意义?

笔者认同这样的观点,人生本无意义,需要我们给予意义。在哲学家们看来,人生的意义最终可以归结为“幸福”二字,幸福是人类一切活动的最高、最终目的。然而,人们对幸福的理解是不一样的。总体而言,大致分为两类,快乐主义幸福观和道德主义幸福观。前者认为幸福在于趋利避害,享受快乐;后者认为幸福在于至善,修德才能得福。但又容易分别走向享乐主义和禁欲主义两个极端。

马克思说:“如果我们选择了最能为人类福利而劳动的职业,那么重担就不能把我们压倒,因为它是为大家而献身;那么我们所感到的就不是可怜的、有限的、自私的乐趣,我们的幸福将属于千百万人,我们的事业将默默地,但是永恒发挥作用地存在下去,而面对我们的骨灰,高尚的人们将洒下热泪。”这启发着我们,人生的意义在于奉献。个人幸福应与集体幸福、社会幸福紧密结合,离开了社会,个人就无所谓幸福可言。

(二)为国为民,侠之大者

在《明报》创刊的第一天,金庸在九龙尖沙嘴那间小小的编辑室中写下:“如果我们能多报道一些社会上美好的事物,如果我们这份小小的报纸能增加读者们生活中的一些喜悦,那将使我们感到很大的幸福。”这里的幸福即是如此。在局势动荡的年代,金庸一手写社评,一手写武侠,本着明辨是非的办报方针,客观报道,客观评论,将《明报》创造成了奇迹。在现实的家国和虚拟的江湖之间,金庸纵横自如。虽然武侠小说本身是娱乐大众的东西,但是金庸将其融入了人生哲理、个人思想、甚至对社会及政治的看法。

所谓“为国为民,侠之大者”,金庸做到了。很多地方将其误写成“侠之大者,为国为民”。笔者认为,其实写作“侠之大者,为国为民”也有一定道理。从诗词创作的角度,这样写符合“上仄下平”的原则,读起来更有美感。然而在原著《神雕侠侣》一书中,金庸确实是将“为国为民”写在前,“侠之大者”写在后。对此应如何解读?这是因为“为国为民”是第一位,是根本目的,也因此成就大侠。而不是去为了获得大侠的名声而做“为国为民”的事,如此就本末倒置了。

(三)大闹一场,悄然离去

庄子说:“吾生也有涯,而知也无涯。”《天龙八部》中逍遥派无崖子的名字即与此相关。其有两个徒弟,丁春秋与苏星河。“春秋”是时间上的无涯,“星河”是空间上的无涯。当人在思考自己在世状态时,会直接感受到世界的无限,与自己的渺小与短暂。人在各个方面都是有限的,一些感官甚至远不如某些种类的动物。“人固有一死”,每个人都有一个共同的大限。史铁生形容“死是一个必然会降临的节日”。金庸将其比喻成“谁也躲不了的瘟疫”。人虽然不能从自然意义上超越死亡,但是按照亚里士多德所云:我们当尽力以求不朽!

有人问金庸人生是什么,金庸说:“人生就是大闹一场,然后,悄然离去。”显然,这里的“闹”不是胡作非为,无法无天的闹,而应该是大放异彩,精彩绝伦的闹。既然我们有足够的运气来到这世间,就应该热热闹闹的,做一番轰轰烈烈的事业,为他人、为社会发光发热,活出人生价值。等到曲终人散,不得不落幕之时再“悄然离去”。我们无法改变死亡这一最终归宿,那么离开时就应当优雅、释然,无所畏惧,不含愧疚地走。同时,悄悄地走,正如悄悄地来,不打扰别人,不给别人添乱。

(四)敝屣荣华,浮云生死

德国哲学家马丁·海德格尔提出“向死而生”的概念,可谓人生意义的真谛。怎么样才是“向死而生”?向死而生需要存在的勇气。梯利希阐述道,存在的勇气就是具有“不顾”性质的自我肯定。它能让我们从人生中源自非存在的种种威胁、困顿与焦虑不安中超拔而出,径直对自己本质性的存在样态做出肯定。

孟子说:“虽千万人吾往矣。”纵然面对千军万马,也要勇往直前,毫无畏惧的冲上去,因为正义在我。如果说萧峰“赤手屠熊搏虎,金戈荡寇鏖兵”是小勇,是匹夫之勇,那么最后他“教单于折箭,六军辟易”则是真正的大勇。因为他心系天下苍生,力求世间和平,早已将生死置之度外,为了忠义二字,以至最后选择以身殉道,令人唏嘘不已。诚然,“人只有自由地去就死,才能赋予存在以至高无上的目标。”

金庸在坚持自己的主张时,也都面对着沉重的压力,有时甚至成为暗杀目标,生命受到威胁,但是他仍然坚持立场,不改初心,后来说道:“是非善恶既已明确,我决不屈服于无理的压力之下。”他在处境危险之时,想到自己武侠小说中的那些大丈夫,就用来勉励自己:“虽然害怕,但不可卑怯退缩,以致被我书中的英雄们瞧不起。”

金庸不朽。“飞雪连天射白鹿,笑书神侠倚碧鸳。”在当今这个“娱乐至死”的年代,有一个快意恩仇、侠肝义胆的江湖供我们回眸反思,何其幸哉!


 

cdq分治+可撤销并查集

1.bzoj 3237 [Ahoi2013]连通图

题意:给一个连通的无向图,无重边无自环,k个询问,每次询问给出不超过4条原图中的边,问将这些边删掉后,无向图是否还是保持连通。一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。

做法:cdq分治+可撤销并查集。每次先加入在右半区间且不在左半区间的边,递归到左半边,撤销,再加入在左半区间且不在右半区间的边,递归到右半边,撤销。

 

未完待续…

诗词中的汉字文化

这篇文章是我上学期汉字文化课的期末作业,为数不多的写作机会,主要是最近两三个月的所思所想。以下是原文:


生活中经常会看到一部分喜欢写诗的同学,把自己写的诗发到朋友圈,往往是用词显得十分古风文雅,或者华丽至极,还可能用上几个典故,最后配上一幅美图,随之就能骗来一堆人的称赞。但如果了解一些近体诗创作的话,就会发现,写的毫无美感。下面是随便在网络上找的一首,作者不详:

月明星稀残枝静,乌鹊寒鸦南北飞。孟德何必挟天子,短歌寥寥亦洒泪。

主旨上,姑且不谈(也不知道想表达什么)。从修辞手法上说也有用典,用了曹操的《短歌行》。再宽容点,前两句就算一个动静结合吧。但是在我看来还是没有美感可言。原因就在于写的完全不符合近体诗的格律!

诗词格律,尤其是近体诗,有三大要素,对仗、平仄、押韵。关于三者分别是什么意思,在此不再赘述。按照格律,上述诗作有两个严重问题:一是韵脚不对,“泪”字出格,“泪”是仄声,这里韵脚必须平声,更严格地说,这里应该押平水韵中的五微韵,和“飞”字同韵。二是全篇出律,且不说是否是七律的平起首句不入韵式,这首诗连基本的“一三五不论,二四六分明”也没有做到,甚至于首句中间一连出现了五个平声。

虽然说好诗未必就不出格、出律,格律工整的也未必就是好诗,但是我还是觉得古诗词读起来之所以有美感,抛开遣词造句来说,与韵律是有很大关系的。为什么“一三五不论,二四六分明”就好听,三平调与孤平要尽量避免,以及为什么会有拗救?这些都是古人智慧的结晶,也是汉字的魅力所在。汉字从前发音分平、上、去、入四声,现在是阴平、阳平、上声、去声四声。汉字的韵律美就在这四声的变化之中,格律即是关于汉字的一大重要发明,使本来朴素的字词连缀成句,读来有抑扬顿挫,循环往复的美感。写诗作词如果全然不顾格律势必会失去汉语的这一巨大优势。就好比写歌,如果曲调没有什么变化,就让人感觉平淡无奇,并不优美,这样歌词写得再好,也仿佛失去了灵魂。即使是写现在的一些文章,想把标题起的文雅一点也可以运用这一规律。

再举一个正面例子,著名歌手、音乐人许嵩在社交平台上写下过这样的句子:“机翼虚无,精通登月。天上名额有限,人间故事大全。”尤其是后两句,虽然用词普通,但很好地注意了写诗的三要素,足够让人吟咏把玩很久。让我想起了黄安《新鸳鸯蝴蝶梦》中的歌词,“在人间已是癫,何苦要上青天”,大概有类似之意。从这一句话足以看出许嵩深厚的文学功底,能写出《庐州月》、《半城烟沙》、《绝代风华》等等这样优秀的古风作品也就不足为奇了。

对联同诗词也是类似,应当尽量遵循旧体规则,凸显汉字之美。当然,如果对于格律有新的发明创造那应该另当别论。以上就是我对诗词中汉字文化的理解。

bzoj 3569 DZY Loves Chinese II

题意:给一个n个点m条边的(连通)无向图,q个询问,每次询问给出k条原图中的边,问将这些边删掉后,无向图是否还是保持连通。一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。\(N\le 100000,M\le 500000,Q\le 50000,1\le K\le 15\)。

这道题实际上是bzoj 3237的加强版。

对原图随便找一个生成树出来,对非树边随机边权,树边边权则为覆盖它的所有非树边权值的异或和,那么一个边集删去后使得图不连通等价于这个边集存在一个子集的权值异或和为0。

随机是为了让边权异或和在不应该是0的情况下不为0。

正确性证明参考这篇 http://dwjshift.logdown.com/posts/2830435

时间复杂度\(O(m+n+32qk)\)

 

 

小清新线段树

小清新线段树的概念是由jiry_2提出的,区别于zkw(重口味)线段树命名。这里我的理解是可以归为一类结合时间复杂度分析以及懒标记应用的非传统线段树。不过既为非传统,这类题目总体来说还是做法各异,下面就结合题目做一些分析。


入门难度

1.bzoj 3211 花神游历各国

区间求和,区间开根号(下取整)

因为只有开根号操作,所以最后不是1就是0,且一个数开根号次数\(O(loglogC)\)级别的,1e9的数最多开5次。所以就怎么暴力都行了,比如判断当前区间最大值是否是1,或者直接记录访问每个节点的次数是否达到5次,用于剪枝。时间复杂度\(O(nlogn+nloglogC)\)。

2.bzoj 3333 排队计划

这个题其实不是很入门

有一个排列,每次修改是给一个位置x,先拿出x及之后所有小于等于a[x]的数,从小到大排序后,再放回空位中,一开始及每次操作完都要输出当前排列的逆序对数。

计算逆序对数就用传统方法,把以每个位置为开头的逆序对数加起来。那么通过观察发现,这个排序操作会抹掉x及之后所有小于等于a[x]的那些位置的贡献,并且不会对其他不动的位置的贡献造成影响。这样每次用线段树通过判断最小值,每次暴力下去找到需要清除贡献的地方即可,因为每个点只会被清除一次,那么平摊下来总时间复杂度就是\(O(nlogn)\)。

 


进阶难度

1.Petrozavodsk Winter-2018. AtCoder Contest I. ADD, DIV, MAX

维护序列,支持区间加,区间整除,区间求最大值。

我们定义线段树上每个节点势能函数为\(W=log_2(Max-Min)\),或者直观理解就是这个区间除以多少次2就会完全相同。那么由于线段树一共\(O(n)\)个节点,初始总势能为\(O(nlogC)\)。因为线段树区间操作会访问\(O(logn)\)个节点,所以一次区间加操作至多增加\(O(lognlogC)\)。由于我们修改时访问一个节点就会使该节点势能减一,所以总的时间复杂度是\(O(nlognlogC)\)。

具体实现就是线段树维护最大值最小值,以及加法的懒标记,对于除法操作如果当前区间的最大值和最小值的改变量是相同的,那么对于这个区间来说,除法操作就可以看成整体加上一个数,否则暴力递归到左右子树。

2.Codeforces 438D The Child and Sequence

维护序列,支持区间求和,区间模一个数,单点修改。

首先需要用一个很好证明的式子\(x\quad mod\quad p<=\frac{x}{2}\),也就是说模操作会让每个数至少除以2。由于只有单点修改,那么就比上一个题好分析了,势能函数是每个区间最大值除以2的次数,初始总势能\(O(nlogC)\),单点修改还是,改变了\(O(logn)\)个点,每个点充能\(O(logC)\),所以总的时间复杂度\(O(nlognlogC)\)。

那么具体实现额外维护最大值,当区间最大值小于模数就剪枝,否则暴力下去。

3.hdu 5306 Gorgeous Sequence

维护序列,区间对一个数取min,询问区间最小值,区间求和

这个题的做法就比较科幻了。

《Segment tree Beats!》课件中关于时间复杂度的证明一些是错误的

可以参考这里,http://jiry-2.blog.uoj.ac/blog/1404

时间复杂度\(O(nlog^{2}n)\)。

 

4.hdu 5634 Rikka with Phi

维护序列,区间赋值,区间取phi,区间求和。

首先根据定义以及相关公式,知道一个大于2的正整数的欧拉函数都是偶数,一个偶数的欧拉函数就至少小了一半,那么一个数能做的次数也就是\(O(logC)\)级别的。

根据前面几个题,这个题的操作就很好想了,如果当前区间的数都相同,那么区间取phi的操作就转化成了区间赋值,同样的打标记即可,不同的话就暴力下去。

时间复杂度是一个log的就比较确信了,然而并不会证。