链接
ICPC World Final 2017 (codeforces gym)
题解
- 网上查题解的时候看到了一道其他题目的结论：“根据歌唱王国的结论，模式串 S 在随机文本串中第一次出现的位置期望为(sum_{bin B}|sum|b)，其中(B)是(S)的Border长度集合。”
- 这个结论或许能直接感性上提示出这道题该怎么做。
- 我们直接考虑将串S的所有Border长度从大到小排成序列(B^{(S)})，我们发现显然(B^{(S)})字典序越大，出现的概率不会变小。
- 但是什么情况下出现概率相等？我们考虑容斥的过程，发现那些长度小于(2|S|-n)的Border压根不会对概率产生影响。所以这些Border我们应该将其踢掉（下文中我们的(B^{(S)})就直接用剔除过无用Border的集合了。）。剩下的东西的字典序相等概率就一定相等。
- 我们有了这样一个结论：我们将串S的所有长度大于等于(2|S|-n)的Border长度从大到小排成序列(B^{(S)})，我们再记串(S)在字符集大小为(k)，长度为(n)的随机串中出现的概率为(P_{n,k}^{(S)})，简记为(P^{(S)})。我们定义(B^{(S)})间的偏序关系为字典序，则(P^{(S)})间的偏序关系和(B^{(S)})间的偏序关系完全相同。
- 至此，这道题已经可以做完了。ACM赛场上一交就过，OI赛场上也可以通过对拍大致验证。
- 但是，怎么证呢？
- 这里曾经有一个证明，可惜他假了。
代码
#include<bits/stdc++.h>
#define LL long long
#define MAXN 101000
using namespace std;
template<typename T> void Read(T &cn)
{
char c; int sig = 1;
while(!isdigit(c = getchar())) if(c == '-') sig = 0;
if(sig) {cn = c-48; while(isdigit(c = getchar())) cn = cn*10+c-48; }
else {cn = 48-c; while(isdigit(c = getchar())) cn = cn*10+48-c; }
}
template<typename T> void Write(T cn)
{
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
if(cn < 0 || cx < 0) {putchar('-'); cn = 0-cn; cx = 0-cx; }
while(cn)cm = cm*10+cn%10,cn/=10,wei++;
while(wei--)putchar(cm%10+48),cm/=10;
putchar(cx+48);
}
template<typename T> void WriteL(T cn) {Write(cn); puts(""); }
template<typename T> void WriteS(T cn) {Write(cn); putchar(' '); }
template<typename T> void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
template<typename T> void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
struct Str{
int b[MAXN+1], ne[MAXN+1];
char c[MAXN+1];
int clen, blen;
int pos;
void getit(int cn)
{
pos = cn;
while(!isalpha(c[1] = getchar())); clen = 1;
while(isalpha(c[++clen] = getchar())); clen--;
}
void get_b(int cn)
{
ne[0] = ne[1] = 0;
for(int i = 2;i<=clen;i++)
{
ne[i] = ne[i-1];
while(ne[i] && c[i] != c[ne[i]+1]) ne[i] = ne[ne[i]];
if(c[i] == c[ne[i]+1]) ne[i]++;
}
blen = 0; int xian = clen;
while(xian) b[++blen] = xian, xian = ne[xian];
while(blen && b[blen] < 2*clen-cn) blen--;
}
inline friend bool operator <(Str &A, Str &B)
{
int lin = min(A.blen, B.blen);
for(int i = 1;i<=lin;i++) if(A.b[i] != B.b[i]) return A.b[i] < B.b[i];
if(A.blen != B.blen) return A.blen < B.blen;
return A.pos < B.pos;
}
void outit() {for(int i = 1;i<=clen;i++) putchar(c[i]); puts(""); }
};
int n,s;
Str a[11];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
Read(n); Read(s);
for(int i = 1;i<=s;i++) a[i].getit(i), a[i].get_b(n);
sort(a+1, a+s+1);
for(int i = 1;i<=s;i++) a[i].outit();
return 0;
}