[再除草]ontak2010:Palindromic Equivalence

。。。事实上我更博客还是很勤的……但是为什么叫除草呢……
因为一直没干正事只好写以前a掉的、难以找题解的题目的题解表示我还是会做正事的233……
题面:

给出一个由小写字母组成的字符串S,问有多少由小写字母
构成的字条串S',满足
1:|S'|=|S|
2:S'[L..R]是回文串,当且仅当S[L..R]是回文串

杜教的百度hi里面是有讲过这题题解的……虽然说就只有一句话,但是已经足以理解这题怎么做了……
我这里只是作一些证明以作补充……方便理解。

先摘录杜教原文:

一个字符串其实就是说明了一大堆相等和不等关系,若有s[i]!=s[j],s[i]!=s[k],那么根据对称性必有s[j]!=s[k],用manacher算法搞出这些关系就好了

首先对于给定的字符串,若是一个回文串,而不是一个回文串,
那么我们就知道构造出来的字符串的子串也要是个回文串,而不是一个回文串。
所以构造出来的字符串一定要满足,且

很显然,如果我们找到了所有的像这样的极大回文子串(易证这些极大回文子串只有O(N)个),那么就能得到一堆相等与不等关系。
显然构造出的字符串合法当且仅当它满足所有约束条件。
继续转化……
首先,如果需要满足相等关系,那么显然i,j在一个联通块里面。
先加入所有相等关系,这样我们就得到了若干连通块,显然同一个连通块的颜色在任意一个构造的字符串里都必须相同。
然后考虑如何满足不等条件。
这样的条件看作连接的无向边。
那么我们就得到了一个无向图。

现在的任务是:用26种颜色给这个图染色,要求相邻点颜色不同,问染色方案数。
显然如果图是一般图的话,这个是目前没有多项式做法的(否则就可以通过二分的方式求图的色数了)。
不过这个图不是一般图……每个联通分量是完全图。
以下是我和xy的聊天记录(删掉了一些影响阅读证明的东西。

Foreseeable 2014/4/14 8:23:27
我终于会靠谱一点证明了
设i<j<k
然后我们已经知道了ai!=ak
那么我们要证明如果有ai!=aj,那么aj!=ak
首先根据连边的策略来看……
ai!=ak,说明[i+1,k-1]是回文串
所以[k-j+i+1,k-1]与[i+1,j-1]恰好成镜像关系
所以[k-j+i+1,k-1]也是回文串
那么根据回文关系……a[k-j+i]=a[j]
Foreseeable 2014/4/14 8:33:32
继续刚才的证明= =
刚才讲到
[k-j+i+1,k-1]也是回文串
那么a[k-j+i]和a[k]的关系只有两种可能
要么a[k-j+i]!=a[k]
那么我们就得到a[k]!=a[j],得证命题
否则a[k-j+i]=a[k]
那么a[j]=a[k]
j和k是在同一个联通块内的
这样总能证明了吧= =
Foreseeable 2014/4/14 8:35:15
终于证明它是弦图了,可喜可贺可喜可贺

弦图自然就随便做了……(见聊天记录

徐毅 2014/4/14 8:40:00
证明了这个东西以后。。就直接i从小到大做。。前面有x个和他不等的。。那么就乘(26 - x)?
Foreseeable 2014/4/14 8:40:14
是啊= =
但是为啥是对的呢
我太逗= =
徐毅 2014/4/14 8:41:36
证了那个性质= = 这样就对了吧。。。因为前面和他不等的已经保证两两互不相等了啊。。。
Foreseeable 2014/4/14 8:41:59
我是逗比
搞了这么久
还是您帮我讲了这道题怎么做
徐毅 2014/4/14 8:43:09
T_T 明明是你帮我证明的!

(以前a过的题目被问到结果忘记怎么做/证了真是……太逗……

Comments

comments powered by Disqus