Tokitsukaze, CSL and Palindrome Game[hdu6791]

发表于 分类于

链接

hdu

题意

对于一个字符串 $S$，我们定义 $E(S)$ 为每次在串后面随机一个小写字母，第一次出现该字符串时的期望次数。

给一个长度为 $n$ 的字符串，$q$ 次询问这个字符串中的两个回文子串，谁的 $E(S)$ 大。

$n,q\le 10^5$

题解

Part 1

考虑，先解决如何计算一个字符串的 $E(S)$。

显然有：$E(S)=\sum_{i=1}^{\infty}P(在i时刻第一次出现S)i$

转换一下得到：$E(S)=\sum_{i=0}^{\infty}P(在i时刻还未出现S)$。

那我们设这么一个字符串集合，表示还未出现S的所有状态，设为 $F$。里面每个字符串有它的出现的概率 $P(F_i)$。

有：$E(S)=\sum P(F_i)$

再设 $G$ 为第一次出现S时的所有状态，同理有 $P(G_i)$。

有：$\sum P(G_i)=1$。

考虑对于 $F$ 集合内的任意一个 $F_i$ ，我们在 $F_i$ 后加上一个 $S$。此时的 ${F_i+S}$ 肯定会包含 $G$。除此以外，有可能在还没有加完整个 $S$ 后就已经出现第一次了，这种情况只能是这个 $S$ 的某个前缀是后缀，也就是border。设这个border长度为 $j$，那么需要再后面加 $|S|-j$ 个数。

那么得到：$\sum P(F_i)(\frac{1}{26})^{|S|}=\sum_{长度为j的border}\sum P(G_i)(\frac{1}{26})^{|S|-j}$

同时乘 $(\frac{1}{26})^{|S|}$，由 $\sum P(G_i)=1$ 得到：

$E(S)=\sum_{j=1}^{|S|}[存在长度为j的border]26^j$

还有另一种证明用的是生成函数，参考2018集训队论文。

Part2

我们将 $E(S)$ 看成 $26$ 进制。那么只需要先比较字符串长度，如果不相等结果就直接出来了。

否则就是比较字典序。

既然是回文子串，就建一个PAM吧！

然后在上面建fail树倍增一下找到询问的字符串。

根据border理论，一个回文串的border也是回文串，对应的刚好就是fail链上的所有长度大于 $0$ 的节点。

那么哈希，然后倍增找到第一个字典序不同的位置即可。

时间复杂度 $O((n+q)\log n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=100010;
const int S=26;
const ll mod=998244853;
const ll base=29;
ll p[N];
int pos[N];
namespace PAM{
	int s[N],n;
	int fa[N],ne[N][S],len[N],siz,las;
	int f[N][20];
	ll h[N];
	vector<int> adj[N];
	void init()
	{
		fo(i,1,n) s[i]=0; s[n=0]=-1;
		fo(i,0,siz) memset(ne[i],0,sizeof(ne[i])),fa[i]=len[i]=0,adj[i].clear();
		siz=1; las=0;
		fa[0]=1; len[1]=-1;
	}
	inline int getfail(int x)
	{
		for(;s[n-1-len[x]]!=s[n];x=fa[x]);
		return x;
	}
	inline int ins(int c)
	{
		s[++n]=c;
		int p=getfail(las);
		if(!ne[p][c])
		{
			int u=++siz,q=getfail(fa[p]);
			len[u]=len[p]+2; fa[u]=ne[q][c]; ne[p][c]=u; 
		}
		las=ne[p][c];
		return las;
	}
	void dfs(int u,int pre)
	{
		if(pre==-1) h[u]=0;
		else h[u]=(h[pre]+(len[u]<=0?0:p[len[u]]))%mod;
		f[u][0]=pre;
		fo(i,1,18)
			if(f[u][i-1]!=-1)
				f[u][i]=f[f[u][i-1]][i-1];
		for(auto v:adj[u]) dfs(v,u);
	}
	void work()
	{
		fo(i,0,siz) if(i!=1) adj[fa[i]].pb(i);
		fo(u,0,siz) fo(i,0,18) f[u][i]=-1;
		dfs(1,-1);
	}
	inline int jump(int u,int k)
	{
		fd(i,18,0) if(f[u][i]!=-1&&len[f[u][i]]>=k) u=f[u][i];
		return u;
	}
	inline int get(int x,int y)
	{
		return jump(pos[y],y-x+1);
	}
	inline int solve(int x,int y)
	{
		fd(i,18,0)
			if(f[x][i]!=-1&&f[y][i]!=-1)
				if((h[x]-h[f[x][i]]+mod)%mod==(h[y]-h[f[y][i]]+mod)%mod)
					x=f[x][i],y=f[y][i];
		if(f[x][0]==-1) return 0;
		return len[x]>len[y]?1:-1;
	}
}
int n;
char s[N];
int main()
{
	p[0]=1;
	ff(i,1,N) p[i]=p[i-1]*base%mod;
	CASET
	{
		n=read();
		scanf("%s",s+1);
		PAM::init();
		fo(i,1,n) pos[i]=PAM::ins(s[i]-'a');
		PAM::work();
		int a,b,c,d,t;
		CASET
		{
			a=read(); b=read(); c=read(); d=read();
			if(b-a+1!=d-c+1)
			{
				puts((b-a+1>d-c+1)?"cslnb":"sjfnb");
				continue;
			}
			t=PAM::solve(PAM::get(a,b),PAM::get(c,d));
			if(t==0) puts("draw");
			else puts((t==1)?"cslnb":"sjfnb");
		}
	}
	return 0;
}