BZOJ 1444:[JSOI2009]有趣的游戏

首先我们建出Trie图，然后高斯消元。

我们设\(f_i\)表示经过第\(i\)个点的期望次数:

\[ f_x=\sum i\cdot p_x(i) \]

\(p_x(i)\)表示经过第\(x\)个点\(i\)次的概率。我们设表示一个单词的节点为关键节点，则所有关键节点只会经过一次，也就是说\(f_{关键}=p_{关键}(1)\)，也就是我们要求的答案。

\[ \displaystyle f_x=\sum_{y与x相连}rate_{y\Rightarrow x}f_y \]

特别地\(\displaystyle f_1=\sum_{y与1相连}rate_{y\Rightarrow 1}f_y+1\)，因为初始点在\(1\)。

\(rate_{y\Rightarrow x}\)就是能从\(y\)走到\(x\)的字母的出现概率。

根据这些等式列方程，再高斯消元就行了。

代码：

#include
    
     #define ll long long#define N 12#define eps 1e-7using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,l,m;double rate[26];double w[N*N][N*N];char str[N];namespace AC_automation {    int cnt=1;    int id[N];    struct trie {        int ch[26];        int w,fail;    }tr[N*N];    void Insert(char *s,int No) {        int len=strlen(s+1),now=1;        for(int i=1;i<=len;i++) {            int j=s[i]-'A';            if(!tr[now].ch[j]) tr[now].ch[j]=++cnt;            now=tr[now].ch[j];        }        id[No]=now;        tr[now].w=1;    }    queue
     
      q;    void build_fail() {        q.push(1);        while(!q.empty()) {            int v=q.front();            q.pop();            for(int i=0;i<26;i++) {                if(!tr[v].ch[i]) continue ;                int sn=tr[v].ch[i],f=tr[v].fail;                while(f&&!tr[f].ch[i]) f=tr[f].fail;                if(!f) tr[sn].fail=1;                else tr[sn].fail=tr[f].ch[i];                q.push(sn);            }        }    }    int find_sn(int now,int j) {        while(now&&!tr[now].ch[j]) now=tr[now].fail;        return now?tr[now].ch[j]:1;    }    void build_matrix() {        for(int i=1;i<=cnt;i++) {            w[i][i]=-1;            if(tr[i].w) continue ;            else {                for(int j=0;j
      
       =1;i--) {        if(fabs(w[i][i])
       
        0.005) cout<
        
         <
         
          <
          <<"\n"; else cout<<"0.00"<<"\n"; } return 0;}