看到这个感觉很牛。
神题啊。
给了你一个值域为 \([1,n]\) 的整数序列 \(A\)，其长度为 \(L\)。
有一个无限长的整数序列 \(B\)，每个数都在 \([1,n]\) 中均匀随机产生。
我们定义 \(B\) 的前缀 \([1,i]\) 是优秀的，当且仅当 \(A\) 是这个前缀的子串。
定义 \(f(B)\) 为 \(B\) 的最短优秀前缀，求 \(f(B)\) 的期望。
首先理解公平赌博的概念，当然只是感性理解。
假设我们有一枚质地均匀的硬币。其抛出后落在正面和反面的概率均为 \(\dfrac{1}{2}\)。
每次你可以花 \(1\) 元下注，接下来我们会将这枚硬币抛出。
若其落在正面，你获得 \(2\) 元。若其落在翻面，你一无所获。
容易发现，在整个过程中，你下注的金额始终为 \(1\) 元，而你得钱的期望为 \(\dfrac{1}{2} \times 0 + \dfrac{1}{2} \times 1 = 1\) 元。
此时你的收益期望为 \(1-1=0\) 元，也就是说期望下你不赚不赔。
我们称这样的情况为公平赌博。
我们发现，在公平赌博下，所有人收益的期望都应该为 \(0\)。也就是说，所有人收益之和的期望也是 \(0\)。
那么我们就可以知道，所有人下注的总金额，与所有人得钱总和的期望，应该是相等的。
接下来回到这一题，我们考虑下面的场景。
你开了一家赌场，规则是这样的。
一个人在第 \(i\) 秒可以花 \(x\) 元下注，并指定一个正整数 \(t\)。
若 \(B_i=t\) 则这个人可以获得 \(nx\) 元，否则这个人一无所获。
接下来我们对赌徒进行安排。
第 \(i\) 秒会有一个赌徒走进你的赌场，他只会带 \(1\) 元钱。
接下来他会拿自己的 \(1\) 元钱下注，赌 \(B_i=A_1\)。
如果这个人赌输了，由于已经无钱可赌，他会退出赌场。
否则这个人会获得 \(n\) 元钱，在第 \(i+1\) 秒他会用这 \(n\) 元钱下注，赌 \(B_{i+1}=A_2\)。
以此类推，假设这个人当前拥有 \(x\) 元钱，则下一秒他会用这 \(x\) 元钱下注，若输了则退出赌场，否则获得 \(nx\) 元钱。
一个人会不断地重复下注的过程，直到其赌输为止。
如果有一个人赌 \(B_x=A_L\) 且其赌赢了，此时我们就可以得到 \(f(B)=x\)。
你已经求出 \(f(B)=x\) 了，接下来就可以把赌场关门了，此时赢钱的人会带着收益离开赌场。
但你还需要思考问题。
考虑对于任何一次下注，由于 \(B\) 是随机产生的，期望得钱为 \(\dfrac{n-1}{n} \times 0 + \dfrac{1}{n} \times nx = x\) 元。
你发现了，这与其下注金额是完全相等的，说明这是一个公平赌博。
对于一个人的多次下注，我们可以将其合并成一次，容易发现此时还是公平赌博。
然后你就发现，一共会来 \(x\) 个人，则下注的总金额就是 \(x\)。
此时我们只要算所有人收益的总和即可。我们发现，如果一个人在第 \(x\) 秒及之前就赌输了，其收益一定为 \(0\)。
否则这个人一定在第 \(x\) 秒赌赢了，假设其已经下注了 \(t\) 次，则其获得的钱为 \(n^t\) 元。
然后你就发现，在上面的规则下，我们对一个人赌的内容建立序列，则这个序列一定是 \(A\) 的前缀。
同时又由于这个人赌的内容直到第 \(x\) 秒都是正确的，而第 \(x\) 秒是子串 \(A\) 的结尾，所以这个序列一定是 \(A\) 的后缀。
所以他赌的序列一定是 \(A\) 的一个公共前后缀。
同理，\(A\) 的每个公共前后缀都对应着一个人。
我们记 \(A:[l,r]\) 表示 \(A\) 中的第 \(l\) 个数到第 \(r\) 个数构成的子串。
此时我们就可以写出问题的答案，即 \(\sum\limits_{A:[1,c]=A:[L-c+1,L]} n^c\)。
使用 KMP 或哈希均可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=10000;
int A[100010],f[100010],pow_n[100010],ans[100010];
int main(){int n,T;scanf("%d %d",&n,&T);while(T--){int L;scanf("%d",&L);pow_n[0]=1;for(int i=1;i<=L;i++){pow_n[i]=pow_n[i-1]*n%mod; scanf("%d",&A[i]);}ans[1]=pow_n[1];for(int i=2;i<=L;i++){f[i]=f[i-1];while(f[i] && A[f[i]+1]!=A[i]){f[i]=f[f[i]];}if(A[f[i]+1]==A[i]){f[i]++;}ans[i]=(ans[f[i]]+pow_n[i])%mod;}printf("%04d\n",ans[L]);}return 0;
}