1152:[CTSC 2006]歌唱王国Singleland題解

(再送信は2012-06-20 の網易ブログ)
 
テーマ: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の接尾辞でもある}
(この言葉はちょっと回りくどい >_
数字列の集合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の解析式は明らかに煩わしくて、2回|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)??? 7 k+何だか銃に当たった・・・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 『具体数学』 私は『具体的な数学』で学んだこの証明書です.