歌唱王国Tokitsukaze, CSL and Palindrome Game[HDU多校3][PAM][数学期望]_综合

文章目录

题目
思路
- 歌唱王国
- Tokitsukaze, CSL and Palindrome Game

题目

Luogu
给定 $S$ ，问随机取数凑出 $S$ 的期望次数
HDU
给定串 $S$ , $Q$ 次询问，每次询问凑出其两个子回文串 $S [l 1 . . . r 1] ， S [l 2 . . . r 2]$ 的期望次数大小比较

思路

歌唱王国

定义 $f_i$ 表示当前已经匹配了 $i$ 个，还期望多少次凑出 $S$
$t r a n s (i, c) :$ $i$ 前缀加上 $c$ 组成的最长能匹配的前后缀
$fail_i:$ 不等于自身的最长前后缀
就是 $K M P$ 自动机和 $A C$ 自动机的东西
$trans(i,c)={i+1c=Si+1trans(faili,c)otherwisetrans(i,c)=\begin{cases} i+1&c=S_{i+1}\\ trans(fail_i,c)& otherwise\\ \end{cases}$
转移，边界如下：
$f_n=0$
$fi=1s∑c=1sftrans(i,c)+1f_i=\frac{1}{s}\sum_{c=1}^sf_{trans(i,c)}+1$
然后发现：
$ffaili=1s∑c=1sftrans(faili,c)+1f_{fail_i}=\frac{1}{s}\sum_{c=1}^sf_{trans(fail_i,c)}+1$
只有 $trans(i,S_{i+1})$ 有变化
即可改写成：
$fi=ffaili?1sftrans(faili,Si+1)+1sftrans(i,Si+1)f_{i}=f_{fail_i}-\frac{1}{s}f_{trans(fail_i,S_{i+1})}+\frac{1}{s}f_{trans(i,S_{i+1})}$
$ffaili?fi=1s(ffaili+1?fi+1)f_{fail_i}-f_{i}=\frac{1}{s}(f_{fail_{i+1}}-f_{i+1})$
记 $g_i=f_{fail_i}-f_{i}$
那么 $gi=gi+1sg_i=\frac{g_{i+1}}{s}$
$g_1=f_{0}-f_{1}$
$f0=1s∑c=1sftrans(0,c)+1=s?1sf0+1sf1+1f_0=\frac{1}{s}\sum_{c=1}^sf_{trans(0,c)}+1=\frac{s-1}{s}f_0+\frac{1}{s}f_1+1$
即 $f_0-f_1=s=g_1$
$g_n=f_{fail_n}-f_n=s^n$
$∵fn=0\because f_n=0$
$∴ffailn=sn\therefore f_{fail_n}=s^n$

$∴ffailfailn=sn+sfailn\therefore f_{fail_{fail_n}}=s^n+s^{fail_n}$
$. . .$
于是 $f_0$ 就能跳 $f a i l$ 求出来了

Tokitsukaze, CSL and Palindrome Game

回文串的 $b o r d e r$ 还是回文的
$A C / K M P$ 自动机的 $f a i l :$ 前缀 $i$ 的 $b o r d e r$ 还是前缀
$S A M$ 后缀自动机的 $f a i l :$ 代表当前点的一些连续后缀集合
$P A M$ 回文自动机的 $f a i l :$ 代表当前回文串的 $b o r d e r$ 还是回文
显然选择 $P A M$
然后倍增之类的
关键是判断大小
可以利用 $H A S H +$ 二分解决

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#include<climits>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
inline int read() {
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c==EOF)exit(0);if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 500000
#define INF 0x3f3f3f3f
ULL p,pw[MAXN+5],Hash[MAXN+5][22];
int pcnt,lst;
int pos[MAXN+5];
char str[MAXN+5];
int fa[MAXN+5][22];
int nxt[MAXN+5][26],fail[MAXN+5],len[MAXN+5];
void Init(){
    pcnt=2,lst=1;memset(fa,0,sizeof(fa));memset(pw,0,sizeof(pw));memset(len,0,sizeof(len));memset(str,0,sizeof(str));memset(nxt,0,sizeof(nxt));memset(fail,0,sizeof(fail));memset(pos,0,sizeof(pos));memset(Hash,0,sizeof(Hash));len[1]=-1,fail[2]=fail[1]=1;return ;
}
void Extend(int c,int n){
    int p=lst;while(str[n-len[p]-1]!=str[n])p=fail[p];if(!nxt[p][c]){
    int u=++pcnt,q=fail[p];len[u]=len[p]+2;while(str[n-len[q]-1]!=str[n])q=fail[q];if(!nxt[q][c])fail[u]=2;else fail[u]=nxt[q][c];nxt[p][c]=u;}lst=nxt[p][c];pos[n]=lst;return ;
}
int Climb(int u,int l){
    for(int i=20;i>=0;i--)if(fa[u][i]&&len[fa[u][i]]>=l)u=fa[u][i];return u;
}
int main(){
    //freopen("play.in","r",stdin);//freopen("play.out","w",stdout);int T=read();while(T--){
    Init();int n=read();scanf("%s",str+1);for(int i=1;i<=n;i++)Extend(str[i]-'a',i);p=127,pw[0]=1;for(int i=1;i<=pcnt;i++)pw[i]=pw[i-1]*p;fail[2]=0,fail[1]=0;len[1]=1,len[2]=1;for(int i=3;i<=pcnt;i++)fa[i][0]=fail[i];//,printf("%d %d %d\n",i,fail[i],len[i]);for(int i=3;i<=pcnt;i++)Hash[i][0]=pw[len[fail[i]]];for(int j=1;(1<<j)<=pcnt;j++)for(int i=1;i<=pcnt;i++)fa[i][j]=fa[fa[i][j-1]][j-1],Hash[i][j]=Hash[i][j-1]+Hash[fa[i][j-1]][j-1];int q=read();while(q--){
    int a=read(),b=read(),c=read(),d=read();int u=Climb(pos[b],b-a+1),v=Climb(pos[d],d-c+1);if(len[u]==len[v]){
    for(int j=20;j>=0;j--)if(fa[u][j]&&fa[v][j]&&Hash[u][j]==Hash[v][j])u=fa[u][j],v=fa[v][j];if(len[fail[u]]==len[fail[v]])puts("draw");else if(len[fail[u]]>len[fail[v]])puts("cslnb");else puts("sjfnb");}else if(len[u]>len[v])puts("cslnb");else puts("sjfnb");}}return 0;
}