LOJ6480 「ICPC World Finals 2017」弄虚作假的塔罗占卜 Tarot Sham Boast 题解

w4p3r · 2020-07-14 12:12:18 · 个人记录

一丶前言：

感谢我们的教练 @jzp1025 的口胡证明与官方题解口胡翻译。

二丶思路：

一道结论好题，假设那个长度为n的随机串是T。

显然，长度为l的字符串s的出现概率为：

（一个简单的容斥，应该看看就懂，注意S是枚举的集合，s字符串）

若|S|=1，这个后面那个求积的结果显然就是3^{-l}。

若|S|=2，假设S=\{ i,j\}(i<j)，若i+l-1<j，求积的结果是3^{-2l}，否则假设t=i+l-j，求积的结果也就是3^{-2l+t}。

可以发现，其实t就是s的一个border。

则x是S的一个border

所以我们可以猜到，正解一定跟border有关（因为暴力去算每个字符串出现的概率显然只有O(n^2)的DP，篇幅原因不再讲解如何DP）

实际上，结论是：

我们把每个s的所有border求出来并从大到小排序，并按这个border序列按字典序从小到大排序。

感性的证明：

为了方便，假设当前字符串为s,其长度为l

假设ans_i=\sum_{S \subset \{ 1,2,..,n-l+1\},|S|=i} \prod_{x \in S}P(T[x,x+|s|-1]==s)

（就是|S|=i时的贡献）

则s出现的概率为：\sum_{i=1}^{n-l+1}(-1)^{i+1}ans_i

略加思考可以发现：

1.所有字符串的ans_1一样（显然）

2.ans_i>=ans_{i+1}（也是显然吧）

根据这两条结论，我们可以发现ans_3到ans_{n-l+1}对答案并没有影响（记住我们是要进行排序，而不是把概率求出来）

那实际上我们比较的就是所有字符串的ans_2，而我们开始就讲了ans_2就是只与border有关的，而且随着border的增大对ans_2的贡献指数级增长（不懂可以重新去看看前面|S|=2的情况）。

而因为ans_2的容斥系数是-1，所以要按字典序从小到大排序。

结束了？不，还要考虑有些border是没用的。

就是在n比较小时，若2*l-x>n(x是s的一个border)，则x这个border并不会对答案造成影响，所以不能加进去。

三丶代码

//Badwaper gg
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register ll
#define fr first
#define sd second
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define lowbit(x) (x&(-x))
#define Z(x) (x>=mod?x-mod:x)
#define N 1000010
#define seed 131
#define mod 998244353
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
int n,S;
ll H[N],Hash[N];
char s[N];string g[N];
pair<vector<int>,int>t[N];
int main()
{
//  freopen("loj6480.in","r",stdin);
//  freopen("loj6480.out","w",stdout);
    n=read(),S=read();H[0]=1;
    FOR(i,1,n)H[i]=1LL*H[i-1]*seed%mod;//要用模数hash，自然溢出被卡了
    FOR(i,1,S)
    {
        scanf("%s",s+1);int len=strlen(s+1);
        FOR(j,1,len)g[i]+=s[j];
        FOR(j,1,len)Hash[j]=(Hash[j-1]+1LL*s[j]*H[j]%mod)%mod;
        vector<int>v;
        REP(j,len-1,0)//求border，从大到小插入
        {
            if(len*2-j>n)continue;
            if(1LL*Hash[j]*H[len-j]%mod==(Hash[len]+mod-Hash[len-j])%mod)v.pb(j);
        }
        t[i]=mp(v,i);
    }
    sort(t+1,t+S+1);//vector默认从大到小排序
    FOR(i,1,S)cout<<g[t[i].second]<<endl;
    return 0;
}

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq