description

周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。

大家纷纷觉得这个游戏非常符合同学们的特色，但只是扔硬币实在是太单调了。

同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币，其他同学记录下正反面情况。

用H表示正面朝上，用T表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比如HTT表示第一次正面朝上，后两次反面朝上。

但扔到什么时候停止呢？大家提议，选出n个同学，每个同学猜一个长度为m的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利，为了保证只有一个同学胜利，同学们猜的n个序列两两不同。

很快，n个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。

data range

\[1≤n,m≤300\]

solution

概率生成函数

\[f(x)=Pr(x=i)x^i\]

\(Pr(x=i)\)表示\(x\)为\(i\)时的概率。

有一个很好的性质:

\[E(x)=\sum_{i=1}^{\infty}iPr(x=i)=f'(1)\]

设\(F_i(x)\)表示关于第\(i\)个序列的成功生成函数，\(G(x)\)表示关于第\(i\)个序列的未成功生成函数，

我们要求的是\(F_i(1)\)。

考虑性质，得出

\[\sum_{i=1}^{n}F_i(x)+G(x)=xG(x)+1\]

\[G(x)(\frac{1}{2}x)^m=\sum_{j=1}^{n}\sum_{k=1}^{m}a_{i,j,k}F_j(x)(\frac{1}{2}x)^{m-k}\]

其中\(a_{i,j,k}\)表示第\(i\)个序列的前\(k\)位是否为第\(j\)个序列的后\(k\)位

对第一个式子求导，得出

\[\sum_{i=1}^{n}F_i'(x)=G(x)\]

将\(x=1\)代入第二个式子，得出

\[G(1)=\sum_{j=1}^{n}\sum_{k=1}^{m}a_{i,j,k}2^kF_j(1)\]

再由

\[\sum_{i=1}^{n}F_i(1)=1\]

这样就有\((n+1)\)个式子可以求解\(F_i(1)\)和\(G(1)\)

code

顺手写了一波从未写过的哈希

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include