【luogu P4548】歌唱王国(期望)(生成函数 / 思维)(KMP)
创始人
2025-06-01 15:09:19

歌唱王国

题目链接:luogu P4548

题目大意

多次询问,每次给你一个字符串,然后有 n 种字符,猴子随机打字。
每个字符打出来的概率相同,然后打出一个串使得给出串是它的子串就停止,问你停止的时候打出来的字符串的期望长度。

思路

首先简单说一下用生成函数的做法:
fif_ifi​ 是长度为 iii 结束的概率,gig_igi​ 是长度为 iii 还没结束的概率。
那一个经典的时候是每个 fif_ifi​ 贡献倍率是 iii,那我们要的答案其实就是 F′(1)F'(1)F′(1)

然后列相关的式子。
首先接下来打了一个字符,分成结束了和没有结束。
xG(i)+1=F(x)+G(x)xG(i)+1=F(x)+G(x)xG(i)+1=F(x)+G(x)

那考虑如果你一直按要求加,加 mmm 次一定能结束,但是可能在之前就结束了,因为有 border。
于是我们设 opiop_iopi​ 是 [1,i][1,i][1,i] 是否是这个串的 border:
G(x)(1nx)m=∑i=1maiF(x)(1nx)m−iG(x)(\dfrac{1}{n}x)^m=\sum\limits_{i=1}^ma_iF(x)(\dfrac{1}{n}x)^{m-i}G(x)(n1​x)m=i=1∑m​ai​F(x)(n1​x)m−i

然后把第一个式子求导:
xG′(i)+G(x)=F′(x)+G′(x)xG'(i)+G(x)=F'(x)+G'(x)xG′(i)+G(x)=F′(x)+G′(x)
F′(x)=(x−1)G′(x)+G(x)F'(x)=(x-1)G'(x)+G(x)F′(x)=(x−1)G′(x)+G(x)

那我们要的是 F′(1)F'(1)F′(1),直接带入:F′(1)=G(1)F'(1)=G(1)F′(1)=G(1)
那也就是要求 G(1)G(1)G(1),那就利用上另一个式子,也带入:
G(1)(1n)m=∑i=1maiF(1)(1n)m−iG(1)(\dfrac{1}{n})^m=\sum\limits_{i=1}^ma_iF(1)(\dfrac{1}{n})^{m-i}G(1)(n1​)m=i=1∑m​ai​F(1)(n1​)m−i
G(1)=∑i=1maiF(1)niG(1)=\sum\limits_{i=1}^ma_iF(1)n^iG(1)=i=1∑m​ai​F(1)ni

考虑 F(1)F(1)F(1) 是多少,那思考一下就是每一项的系数加起来,那所有长度结束的概率的和不就是 111 嘛。

ans=F′(1)=G(1)=∑i=1mainians=F'(1)=G(1)=\sum\limits_{i=1}^ma_in^ians=F′(1)=G(1)=i=1∑m​ai​ni

不难扩展出当每个字符不一样概率的时候,那每个字符概率是 pip_ipi​,给出字符串是 bib_ibi​,那就是:
ans=F′(1)=G(1)=∑i=1mai(∏j=1ipbi)ans=F'(1)=G(1)=\sum\limits_{i=1}^ma_i(\prod\limits_{j=1}^ip_{b_i})ans=F′(1)=G(1)=i=1∑m​ai​(j=1∏i​pbi​​)


然后说人类智慧。
这是一个有关鞅(martingale)的方法,不过我们可以把它具象成公平赌博中的博弈。

考虑这么一个赌场,每天选择的字符按顺序是你要求的字符,每天会有一个新人进来,一开始他只有一块钱,他也会按你要求的字符按顺序每天赌,会把全部钱都拿来赌,赔率是 1:1:1:这个字符出现概率的倒数,赌输了就走。
然后赌场把字符放完就让所有人滚。

首先赔率显然没问题,因为要公平。
那接着你注意到是公平博弈,所以赌场要不赚不亏。
那我们可以看赚钱的人总共赚了多少。
那就是:

w=∑[1,i]isbordermai(∏j=1ipbi)w=\sum\limits_{[1,i]is\ border}^ma_i(\prod\limits_{j=1}^ip_{b_i})w=[1,i]is border∑m​ai​(j=1∏i​pbi​​)

那赌场要不亏不赚,那进来的钱是多少,是人数,其实也就是字符串长度。
那赌场应该让 www 个人进来,那就是字符串的期望长度就是 www。

(在鞅的角度大概是你每个时刻每个赌徒的钱数是一个商,然后所有赌徒钱加起来的值 MiM_iMi​ 也是鞅)
(然后 TTT 是判断要不要停下来的停时 {T=n}\{T=n\}{T=n},然后有个可选停止定理有 EMT=EM0\mathbb{E}M_T=\mathbb{E}M_0EMT​=EM0​)
(那一开始 M0=0M_0=0M0​=0,所以 ET=MT\mathbb{E}T=M_TET=MT​)
小孩子不懂事瞎说的


那实现很简单,直接每次建 KMP,然后跳 fail 即可。

代码

#include
#define mo 10000using namespace std;const int N = 1e5 + 100;
int n, t, m, a[N], fail[N], cf[N];int main() {scanf("%d %d", &n, &t);cf[0] = 1; for (int i = 1; i < N; i++) cf[i] = cf[i - 1] * n % mo;while (t--) {scanf("%d", &m);for (int i = 1; i <= m; i++) scanf("%d", &a[i]);int j = 0;for (int i = 2; i <= m; i++) {while (j && a[j + 1] != a[i]) j = fail[j];if (a[j + 1] == a[i]) j++; fail[i] = j;}int ans = 0;for (int now = m; now; now = fail[now]) (ans += cf[now]) %= mo;if (ans < 1000) printf("0");if (ans < 100) printf("0");if (ans < 10) printf("0");printf("%d\n", ans);}return 0;
}

相关内容

热门资讯

重磅来袭“小米麻将有挂吗 ”详... 您好:小米麻将这款游戏可以开挂,确实是有挂的,需要了解加客服微信【5537821】很多玩家在这款游戏...
重磅.通报“ 胡乐麻将 透视... 您好:胡乐麻将这款游戏可以开挂,确实是有挂的,需要软件加微信【3398215】很多玩家在这款游戏中打...
玩家必看“神皇大厅到底能开挂吗... 您好:神皇大厅这款游戏可以开挂,确实是有挂的,需要了解加客服微信【8383742】很多玩家在这款游戏...
今日重大通报“天酷斗牛是不是有... 您好:天酷斗牛这款游戏可以开挂,确实是有挂的,需要软件加微信【4770480】,很多玩家在天酷斗牛这...
科技通报“决胜奕福确实可以开挂... 亲.决胜奕福这款游戏是可以开挂的,确实是有挂的,通过添加客服【3671900】很多玩家在这款游戏中怀...