自动机+高斯消元 ifrog1025 Magic boy Bi Luo with his excited

传送门：点击打开链接

题意：告诉你ｎ个串，现在随机写字符，直到之前的字典里某个差un是当前写的串的子串时停止，问期望次数是多少．

思路：玲珑套路杯，求个自动机发现next数组就是接下来的状态,套个高斯消元就做完了..

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;

const int MX = 150 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

LL power(LL a,LL b) {
    LL ret = 1;
    while(b) {
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
typedef LL Matrix[MX][MX];
void gauss(Matrix A,int n) {
    int i,j,k,r;
    for(i = 0; i < n; i++) {
        r = i;
        for(j = i + 1; j < n; j++) {
            if(abs(A[j][i]) > abs(A[r][i])) r = j;
        }
        if(r != i) for(j = 0; j <= n; j++) swap(A[r][j],A[i][j]);

        for(k = i + 1; k < n; k++) {
            LL f = A[k][i] * power(A[i][i],mod - 2) % mod;
            for(j = i; j <= n; j++) A[k][j] = (A[k][j] - f * A[i][j]) % mod;
        }
    }

    for(i = n - 1; i >= 0; i--) {
        for(j = i + 1; j < n; j++) {    
            A[i][n] = (A[i][n] - A[j][n] * A[i][j]) % mod;
        }
        A[i][n] = A[i][n] * power(A[i][i],mod - 2) % mod;
    }
}
struct AC_machine {
    int rear,root;
    int Next[MX][26],Fail[MX],End[MX];
    void Init() {
        rear = 0;
        root = New();
    }
    int New() {
        End[rear] = 0;
        for(int i = 0; i < 26; i++) {
            Next[rear][i] = -1;
        }
        return rear++;
    }
    void Add(char *A) {
        int n = strlen(A),now = root;
        for(int i = 0; i < n; i++) {
            int id = A[i] - 'a';
            if(Next[now][id] == -1) {
                Next[now][id] = New();
            }
            now = Next[now][id];
        }
        End[now] = 1;
    }
    void Build() {
        queue<int> Q;
        Fail[root] = root;
        for(int i = 0; i < 26; i++) {
            if(Next[root][i] == -1) {
                Next[root][i] = root;
            } else {
                Fail[Next[root][i]] = root;
                Q.push(Next[root][i]);
            }
        }
        while(!Q.empty()) {
            int u = Q.front(); Q.pop();
            if(End[Fail[u]]) End[u] = 1;
            for(int i = 0; i < 26; i++) {
                if(Next[u][i] == -1) {
                    Next[u][i] = Next[Fail[u]][i];
                } else {
                    Fail[Next[u][i]] = Next[Fail[u]][i];
                    Q.push(Next[u][i]);
                }
            }
        }
    }
    void matrix(Matrix A) {
        for(int i = 0; i < rear; i++) {
            for(int j = 0; j <= rear; j++) A[i][j] = 0;
        }
        LL p = power(26,mod - 2);
        for(int i = 0; i < rear; i++) {
            if(End[i]) {
                A[i][i] = 1;
                continue;
            }
            int s = 26;
            for(int j = 0; j < 26; j++) {
                int v = Next[i][j];
                if(v == i) s--;
                else A[i][v] = (A[i][v] + p) % mod;
            }
            A[i][i] = -(LL)s * p % mod;
            A[i][rear] = -1;
        }
    }
} AC;

int n;
char tmp[MX];
Matrix A;

LL solve() {
    AC.matrix(A);
    int w = AC.rear;
    gauss(A,w);
    LL ans = (A[0][w] + mod) % mod;
    return ans;
}

int main() {
    // FIN;
    int T,ansk = 0;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        AC.Init();
        for(int i = 1; i <= n; i++) {
            scanf("%s",tmp);
            AC.Add(tmp);
        }
        AC.Build();
        printf("Case #%d: %lldn",++ansk,solve());
    }
    return 0;
}

（编辑：辽源站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!