bzoj1152: [CTSC2006]歌唱王国Singleland

这。。是一题神题，我就不多说了，太神了（对于我来说）

太弱了，众神犇可望不可即

题解：

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

 

用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即可。

intres = 0;

for(intcur = m; cur != 0; cur = back[cur])

res = (res + qpow(n, cur)) % Mod;

 

好了，代码完全抄袭某神

const int N = 100010, Mod = 10000;
int n, T;
int m, Dat[N], Last[N];
int Cnt[N], Flag;

inline void Solve() ;

inline void Input() {
	scanf("%d%d", &n, &T), n %= Mod;
	while(T--) {
		scanf("%d", &m);
		Rep(i, m) scanf("%d", &Dat[i]);
		Solve();
	}
}

inline void Solve() {
    Last[0] = -1;
    rep(i, 1, m)
	    for(int t = Last[i-1]; ; t = Last[t]) {
		    if(Dat[t+1] == Dat[i]) {
				Last[i] = ++t;
				break;
			}
		    if(t == -1) {
				Last[i] = t;
				break;
			}
		}
	
	++Flag;
    for(int x = m-1; x != -1; x = Last[x]) Cnt[x] = Flag;
    int tmp = n, Ans = 0;
	Rep(i, m) {
	    if(Cnt[i] == Flag) Ans = (Ans+tmp) % Mod;;
	    tmp = (tmp*n) % Mod;
	}
    printf("%04d\n", Ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1152");
	#endif
	Input();
	/* Solve(); */
	return 0;
}