自动机+高斯消元 ifrog1025 Magic boy Bi Luo with his excited
发布时间:2021-01-31 13:35:14 所属栏目:大数据 来源:网络整理
导读:传送门:点击打开链接 题意:告诉你n个串,现在随机写字符,直到之前的字典里某个差un是当前写的串的子串时停止,问期望次数是多少. 思路:玲珑套路杯,求个自动机发现next数组就是接下来的状态,套个高斯消元就做完了.. #include map#include set#include
传送门:点击打开链接 题意:告诉你n个串,现在随机写字符,直到之前的字典里某个差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; } (编辑:威海站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |