注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

1152: [CTSC2006]歌唱王国Singleland 题解  

2012-06-20 23:57:05|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目见:http://www.lydsy.com/JudgeOnline/problem.php?id=1152

话说在前……有公式恐惧症的勿读此文……

用pow(a, b)代表a的b次方。
用Σ(a, b)代表条件为a,对b求和。
用|a|代表字符串a的长度。
用a . b代表数字串a和数字串b串联后的字符串。
而a + b代表数字串集合a与数字串集合b的并集。
数字a既可当数字a也可当只包括a的数字串。
数字串a既可当数字串a也可当只包括a的数字串集合。

设名字为数字串s
设数字串集合P = {a | a是s的后缀 且 a≠空串 且  a≠s 且 s去掉a这个后缀后,剩下的字符串既是s的前缀也是s的后缀}
(这句话有点绕 >_< 比如12121,121既是12121的前缀也是12121的后缀)
设数字串的集合Y。Y是所有以s结尾的且之前未出现过s的数字串的集合。
用A[i]代表数字串集合A中长度为i的数字串的个数。
用expect代表平均歌唱时间。

好了……终于可以很方便地说话了。

题目就是要求expect,看看expect与Y的关系:expect = Σ(a ∈Y, |a| * pow(1 / n, |a|))
定义一个对数字串集合的函数:f(A) = Σ(a ∈A, |a| * pow(1 / n, |a|))
则expect = f(Y)

那么想办法来求f(Y)。
设数字串集合N,N是不包含s的数字串的集合。
我们辅助N来表示Y

空串 + Σ(a ∈ N, Σ(1 ≤ i ≤ n, a . i)) = N + Y
Σ(a ∈ N, a . s) = Y + Σ(a ∈ Y, Σ(p ∈ P, a . p))

但是f的解析式显然太烦人了,出现了两次|a|,刚才的方程几乎没啥用。
于是我们再定义一个函数g(A, z) = Σ(a ∈A, pow(1 / n * z, |a|),
那么g(A, z)对z的导数g'(A,z) = Σ(a ∈A, |a| * pow(1 / n, |a|) * pow(z, |a| - 1)),于是得到:f(A) = g'(A, 1)
所以说我们要求f(Y),求g'(Y, z)的解析式就是了;我们要求g'(Y, z),求g(Y, z)的解析式然后再求导就是了。
(g(Y, z)??? 7k+莫名中枪……orz 7k+!!!)

好的,那么现在来尝试着根据之前的方程来求g(Y, z)。重新列方程:
g(空串 + Σ(a ∈ N, Σ(1 ≤ i ≤ n, a . i)), z) = g(N + Y, z)
g(Σ(a ∈ N, a . s), z) = g(Y + Σ(a ∈ Y, Σ(p ∈ P, a . p)), z)

因为若a、b是数字串集合,则g(a + b, z) = g(a, z) + g(b, z) (这个显然吧……)
若a是数字串集合,b是数字串,则g(Σ(i ∈ a, i . b), z) = g(a, z) * pow(1 / n * z, |b|)(这个也显然吧……)
所以:
g(空串, z) + g(N, z) * (Σ(1 ≤ i ≤ n, pow(1 / n * z, 1))) = g(N, z) + g(Y, z)
g(N, z) * pow(1 / n * z, |s|) = g(Y, z) + g(Y, z) * g(P, z)

所以:
1 + g(N, z) * z = g(N, z) + g(Y, z)
g(N, z) * pow(1 / n * z, |s|) = g(Y, z) + g(Y, z) * g(P, z)

好了……使劲解解方程,得到:
g(Y, z) = pow(1 / n * z, |s|) / (pow(1 / n * z, |s|) - z + 1 - z * g(P, z) + g(P, z))
现在想求g'(Y, 1),不妨令h(z)为分子, q(z)为分母
则h(1) = pow(1 / n, |s|)
q(1) = pow(1 / n, |s|)

h'(z) = |s| * pow(z, |s| - 1) * pow(1 / n, |s|)  所以  h'(1) = |s| * pow(1 / n, |s|)
q'(z) |s| * pow(z, |s| - 1) * pow(1 / n, |s|) - 1 + 0 - Σ(a ∈P, (|a| + 1) * pow(z, |a|) * pow(1 / n, |a|)) + Σ(a ∈P, |a| * pow(z, |a| - 1) * pow(1 / n, |a|)) 所以 q'(1) = |s| * pow(1 / n, |s|) - 1 - Σ(a ∈P, pow(1 / n, |a|))

现在来算g'(Y, 1):
   g'(Y, 1)
= (h'(1) * q(1) - h(1) * q'(1)) / (q(1) * q(1))
= (|s| * pow(1 / n, |s|) * pow(1 / n, |s|) - pow(1 / n, |s|) * |s| * pow(1 / n, |s|) - 1 - Σ(a ∈P, pow(1 / n, |a|))) / (pow(1 / n, |s|) * pow(1 / n, |s|))
= (1 + Σ(a ∈P, pow(1 / n, |a|))) / pow(1 / n, |s|)
= pow(n, |s|) + Σ(a ∈P, pow(n, |s| - |a|))

|s| - |a|?于是我们得到公式:
expect = f(Y) = g'(Y, 1) = Σ(a ∈P且a既是s的前缀也是s的后缀, pow(n, |a|))

求每个a用KMP即可。
int res = 0;
for (int cur = m; cur != 0; cur = back[cur])
res = (res + qpow(n, cur)) % Mod;

终于写完了 T_T 这题简直就是数学题啊啊啊!!可能会有式子不小心打错,大神勿喷啊……
顺带一说,我刚才用的g其实有个很厉害的名称……叫做概率母函数。
orz 《具体数学》 我是在《具体数学》上学到的这题证明。
  评论这张
 
阅读(1485)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017