题解 P3706 【[SDOI2017]硬币游戏】

目前应该是你站里跑的最快的代码，吸氧后仅需 60ms _(不吸氧的话240ms,但是在这份代码之前的代码都是吸过氧才跑的比我快的233)_ 真是一道神题…… ## 暴力 我们对所有的模式串建一只trie图 就变成了经典的图上随机游走求到达每一个点概率的问题 然后我们可以暴力的列方程，高斯削元，算法复杂度$O(n^3m^3)$不可接受 _(如果你不是很熟练的话，可以忽略这个暴力，因为掌握正解不需要掌握暴力)_ 当问题变得辣手的时候，我们需要想一些机智的办法 # 本题题解 我们的思路是这样的 _令$p(i)$表示第i个人获胜的概率_ 我们发现最后游戏结束时的字符串肯定是一个不可匹配任意一个串的串+一个模式串 那么我们发现直接求这个不可匹配串+模式串的出现概率是极其不好求的，因为我们对这个串基本一无所知，所以也根本计算不了概率 ~~(因为这就是答案啊……233)~~ 但是，不知道大家小学的时候有没有学过这样的一种列方程技巧 一开始先摆出一个毫无争议的等式 比如 **xx的总数=xx的总数** 然后等式两边换不同的形式表达这个"总数"于是便可以神奇的解出x 我们在这道题里也会采取类似的思路 从3个毫无争议的等式开始 #### 任意串出现的概率=任意串出现的概率 #### a+b串出现的概率=a出现的概率×b出现的概率 #### 所有模式串出现的概率相等 我们可以推出 ### (任意串+任意模式串)出现的概率=(任意串+任意模式串)出现的概率 现在要做的就是如何表达这个显而易见的式子 我们发现，任意串+模式串i可以由使点j胜利的串+一些其他的字符串表示 所以我们枚举这个(任意串+模式串i)是由哪一个使j胜利的串表示的 这样我们可以列出n个等式，而使j胜利的串出现的概率=$P(j)$我们就可以解方程解出$P(j)$了 我们发现每个使j胜利的串都可以直接怼上一个模式串i来达成任意串+模式串i的形式。这种情况太trival了，所以我们对于每一个等式都减去这个trival情况出现的概率，此时等式依然成立 排除了这种情况，我们会发现此时我们可以通过使j胜利的串+一些字符串的形式来构造一个任意字符串+模式串i形式的字符串。 并且我们会发现，此时被构造出来的串中的模式串部分(就是被构造的串的**长度为m的**后缀)一定有一个前缀，是**使j胜利的串的**一个后缀，(换句话说，这个前缀和后缀相等，显然这个前缀和后缀长度小于m) 而我们发现，**使j胜利的串的长度为m的**后缀，是模式串j。 换句话来讲，只要我们的模式串j的一个后缀=模式串i的一个前缀，并且这个前缀(或者后缀)长度=k，我们就可以通过给一个使j胜利的串后添加m-k个字符的方式构造出一个任意字符串+模式串i形式的字符串 (如果看不懂以上描述，可以看图)  由于绿色+浅蓝色部分=红色部分，我们可以推出深蓝色部分=紫色部分 而深蓝色部分是j的后缀，紫色部分是i的前缀 那么我们现在可以枚举公共前后缀，从而求出由模式串j+特定字符串构造出任意串+模式串i形式的字符串的概率(假设i，j的前的第k个公共前后缀长度为$len_{i,j,k}$) 那么我们可以得到这样一个式子 ## $P(N+i)=\sum_{j=1}^{n}\sum_{k=1}^{n}2^{(m-len_{i,j,k})}P(j)$ 其中$P(N+i)$表示任意串+模式串i形式的串出现的概率，P(j)已经定义过了 方程的意义就是为了构造i我们枚举j，枚举i，j的公共前后缀k，在j后添加一个长度为$m-len_{i,j,k}$的特定字符串从而构造了一个任意串+模式串i形式的串 还记的我们一开始摆出的毫无争议的等式吗？，他可以写成这样 ### $P(N+1)=P(N+2)=……P(N+n-1)=P(N+n)$ 于是我们有了N个等式，但是我们发现有N+1个变量……(最后一个变量是我们设的$P(N+i)的值$) 没关系，我们此时暴力高斯削元可以把$P(j)$用$P(N+i)$表示，也就是说我们知道各个$P(j)$间的比例关系 此时仔细观察还有一个隐藏的等式 ## $\sum_{i=1}^{n}P(i)=1$ 我们已经知道各个p的比例关系，直接按比例分配就行了 ## 关于枚举i，j的公共前后缀问题 上述的算法已经成功的将时间复杂度降到了$O(n^3)$ 但是会有一个问题，如何枚举i，j的公共前后缀？ 一种可行的做法是接在一起跑kmp，然后通过跳next数组的方式来玄学的枚举公共前后缀 但是你们不觉得kmp的next十分玄学，而且不好把控吗……?而且不觉得每次跑一边kmp麻烦吗？ # 为什么不试试神奇的hash呢？ hash又好写又好调,还很好理解，不知道比kmp高到哪里去了。 而且关键是我们可以预处理每个前缀和后缀的hash值，此时只需枚举i，j和公共前缀的长度k，**常数极小**(当然这也是为什么这份代码跑的比香港记者还快的原因了) 然后我们就可以列方程然后去解了…… 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std; const int N=310;typedef double db;const db eps=1e-10; typedef long long ll;ll mod[2]={998244353,1e9+7}; ll mi[2][N];ll inv[2][N];int n;int m;db len[N];db res; ll key[2][N][N];ll hash[2][N];char mde[N];db t[N][N]; int main() { scanf("%d%d",&n,&m);len[0]=1;//保险起见用了双hash，欧皇们可以尝试单hash inv[1][0]=inv[0][0]=mi[1][0]=mi[0][0]=1; for(int i=1;i<=m;i++){len[i]=len[i-1]*0.5;} for(int i=1;i<=m;i++){mi[0][i]=(mi[0][i-1]*4LL)%mod[0];}//打表次幂 for(int i=1;i<=m;i++){mi[1][i]=(mi[1][i-1]*4LL)%mod[1];} for(int i=1;i<=m;i++){inv[0][i]=(inv[0][i-1]*748683265LL)%mod[0];}//打标逆元 for(int i=1;i<=m;i++){inv[1][i]=(inv[1][i-1]*250000002LL)%mod[1];} for(int z=1;z<=n;z++) { scanf("%s",mde+1);//处理出前缀和后缀的hash值 for(int i=1;i<=m;i++){hash[0][i]=(hash[0][i-1]+((mde[i]=='H')+1)*mi[0][i-1])%mod[0];} for(int i=1;i<=m;i++){hash[1][i]=(hash[1][i-1]+((mde[i]=='H')+1)*mi[1][i-1])%mod[1];} for(int i=1;i<=m;i++){key[0][z][i]=hash[0][i]*hash[1][i];}//前缀hash for(int i=1;i<=m;i++) { ll val0=((hash[0][m]+mod[0]-hash[0][i-1])*inv[0][i-1])%mod[0]; ll val1=((hash[1][m]+mod[1]-hash[1][i-1])*inv[1][i-1])%mod[1]; key[1][z][m-i+1]=val0*val1;//后缀hash } } for(int i=1;i<=n;i++)//暴力枚举i,j,k列方程 { for(int j=1;j<=n;j++) { for(int k=1;k<=m;k++)//判一下hash值是否相等 {if(key[0][i][k]==key[1][j][k]){t[i][j]+=len[m-k];}} } } for(int i=1;i<=n;i++){t[i][n+1]=1;}//这里用单位1来代替P(N+i)了 for(int i=1;i<=n;i++)//高斯削元的板子，不会的话出门左转luogu膜板区 { if(-eps<t[i][i]&&t[i][i]<eps) { for(int j=i+1;j<=n;j++) { if(-eps<t[j][i]&&t[j][i]<eps){continue;} for(int k=1;k<=n+1;k++){swap(t[j][k],t[i][k]);}break; } } db div=t[i][i];for(int k=1;k<=n+1;k++){t[i][k]/=div;} for(int j=1;j<=n;j++) { if(j==i||(-eps<t[j][i]&&t[j][i]<eps)){continue;} db mult=t[j][i];for(int k=1;k<=n+1;k++){t[j][k]-=mult*t[i][k];} } } for(int i=1;i<=n;i++){res+=t[i][n+1];}//按比例分配一下就是答案 for(int i=1;i<=n;i++){printf("%.10lf\n",t[i][n+1]/res);}return 0;//拜拜程序~ } ```