Description：

字符集大小为 $N$ ，给定串 $S$ ，求：一个随机序列中 $S$ 第一次出现的位置期望。

$N,|S|\leqslant10^5$

Solution：

设 $F(x)$ 为表达结束时序列长度的概率生成函数，那么答案就是 $F'(1)$ 。

定义一个辅助生成函数 $G(x)$ 为序列到达 $i$ 还没有结束的概率。

那么有： $$ [x^n]F(x)=[x^{n-1}]G(x)-[x^n]G(x)+[n=0] $$ 那么也就有： $$ F(x)+G(x)=1+G(x)\times x $$ 设 $a$ 为一个 $0/1$ 序列，其中第 $i$ 项表示 $[1,i]$ 是否是一个 $border$ ，定义字符串长度为 $l$ ，字符集为 $\Sigma$ ，那么有： $$ G(x)\times (\frac 1mx)^L=\sum_{i=1}^LF(x)a_i (\frac 1mx)^{L-i} $$ 这个式子的意义就是，我们往一个还没结束的字符串后面再加这个字符串，那么这样生成的字符串 $S$ 一定出现过（最后 $S$ 个字符），但是不一定是第一次出现，但是第一次出现一定和最后一次出现相交，那么我们可以枚举相交的长度 $i$ ，他一定是原串的一个 $border$ 。

将第一个式子两边求导： $$ F'(x)+G'(x)=G'(x)\times x+G(x)\Longrightarrow F'(1)=G'(1)\times 1+G(x)-G'(1)+G(1)=G(1) $$ 于是我们只要求 $G(1)$ 就行了。

再把 $x=1$ 代入第二个式子： $$ G(1)=\sum_{i=1}^LF(1)a_im^i=\sum_{i=1}^La_im^i $$ 就可以在 $O(L)$ 的时间内求解了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int m,n,t;

#define MAXN 100010

int s[MAXN];

bool v[MAXN];

int nxt[MAXN];

#define MOD 10000

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % MOD)if(b & 1)res = 1ll * res * a % MOD;

	return res;

}

int main()

{

	scanf("%d%d",&m,&t);

	while(t--)

	{

		scanf("%d",&n);

		for(int i = 1;i <= n;++i)scanf("%d",&s[i]);

		for(int i = 2,j = 0;i <= n;++i)

		{

			while(j && s[i] != s[j + 1])j = nxt[j];

			if(s[i] == s[j + 1])++j;

			nxt[i] = j;

		}

		int cur = n;

		v[n] = true;

		while(nxt[cur] != 0)

		{

			v[nxt[cur]] = true;

			cur = nxt[cur];

		}

		int ans = 0;

		for(int i = 1;i <= n;++i)ans = (ans + v[i] * power(m,i)) % MOD;

		if(ans < 1000)putchar('0');

		if(ans < 100)putchar('0');

		if(ans < 10)putchar('0');

		printf("%d\n",ans);

		for(int i = 1;i <= n;++i)v[i] = false;

	}

	return 0;

}