首页 > 代码库 > ZOJ 2619 Generator (概率、AC自动机、高斯消元)
ZOJ 2619 Generator (概率、AC自动机、高斯消元)
Generator
题目:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2619
题意:给定一个数N,代表可以选前N个字母。然后给定一个仅有前N个字母组成的字符串,问从空串开始构造,每次可以在已有基础上从前N个字母中挑选一个加在后面,问构造的字符串的长度期望是多少?
思路:如果给定的串长度为L,那么对于构造的串,对应的状态就是0到L之间的数。如果为L即为构造成功。记F[i] 为从i状态到达L状态期望的步数,那么对于0到L-1中的每个i,可以列出一个状态转移:
F[i] = 1 + 1 / n * ΣF[Ci,j] (其中Ci,j 表示在i状态末尾添加第j个字母之后,得到的新状态。
1. 上面可以得到一个方程组,解的的F[0]即为答案(PS 这道题用double解高斯消元过不了,所以要用解整数的高斯消元)
2. Ci,j 的实质是求给定字符串的第i个前缀添加字母后变成哪一个前缀,可以用AC自动机来预处理。
代码:
/* ID: wuqi9395@126.com PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, n) for (int i = 0; i < n; i++) #define debug puts("===============") #define eps 1e-6 typedef long long ll; typedef unsigned long long ULL; using namespace std; const int maxn = 15; long long a[maxn][maxn] = {0}, ans[maxn] = {0}; bool l[maxn]; int n; inline int solve(long long a[][maxn], bool l[], long long ans[], const int& n) { int res = 0, r = 0; for (int i = 0; i < n; i++) l[i] = false; for (int i = 0; i < n; i++) { for (int j = r; j < n; j++) if (a[j][i] != 0) { for (int k = i; k <= n; k++) swap(a[j][k], a[r][k]); break; } if (a[r][i] == 0) { res++; continue; } for (int j = 0; j < n; j++) if (j != r && a[j][i] != 0) { if (a[j][i] < 0) { for (int k = 0; k <= n; k++) a[j][k] *= -1; } long long gcd = __gcd(a[r][i], a[j][i]); long long lcm = a[r][i] / gcd * a[j][i]; long long jmul = lcm / a[j][i]; long long imul = lcm / a[r][i]; for (int k = 0; k <= n; k++) { a[j][k] = a[j][k] * jmul - a[r][k] * imul; } } l[i] = true, r++; } for (int i = r; i < n; i++) if (a[i][n] != 0) return -1; for (int i = 0; i < n; i++) if (l[i]) for (int j = 0; j < n; j++) if (a[j][i] != 0) ans[i] = a[j][n] / a[j][i]; return res; } const int maxnode = 15 * 26; int charset; struct ACAutomaton { int ch[maxnode][26]; int fail[maxnode]; int Q[maxnode]; int val[maxnode]; int sz; int ID[128]; void init() { fail[0] = 0; for (int i = 0; i < 26; i++) ID[i + 'A'] = i; } void reset() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } void Insert(char* s, int key) { int u = 0; for (; *s; s++) { int c = ID[*s]; if (!ch[u][c]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] = key; } void Construct () { int *s = Q, *e = Q; for (int i = 0; i < charset; i++) { if (ch[0][i]) { *e++ = ch[0][i]; fail[ch[0][i]] = 0; } } while(s != e) { int u = *s++; if (val[fail[u]]) val[u] = 1; for (int i = 0; i < charset; i++) { int &v = ch[u][i]; if (v) { *e++ = v; fail[v] = ch[fail[u]][i]; } else { v = ch[fail[u]][i]; } } } } void work() { double t = 1.0 / charset; //cout<<charset<<endl; for (int i = 0; i < sz - 1; i++) { a[i][i] += charset, a[i][sz - 1] += charset; for (int j = 0; j < charset; j++) { if (!val[ch[i][j]]) { //cout<<i<<" "<<ch[i][j]<<endl; a[i][ch[i][j]] -= 1; } } } } } AC; int main () { int n, t, cas = 1; char str[15]; scanf("%d", &t); AC.init(); while(t--) { scanf("%d%s", &n, str); AC.reset(); charset = n; AC.Insert(str, 1); memset(a, 0, sizeof(a)); AC.Construct(); //得到状态转移 AC.work(); //构造方程 solve(a, l, ans, AC.sz - 1); if (cas != 1) putchar('\n'); printf("Case %d:\n%lld\n", cas++, ans[0]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。