首页 > 代码库 > UVA 1358 - Generator(dp+高斯消元+KMP)
UVA 1358 - Generator(dp+高斯消元+KMP)
UVA 1358 - Generator
题目链接
题意:有m种字符(从‘A‘开始往后数的大写字母),现在有一个字符串,长度不超过12,现在每次随机生成一个字母,要求能产生该字符串的期望长度
思路:dp[i]表示产生长度i的期望长度,那么每次产生一个字符,对应m种转移,每种转移的概率为1/m,转移后的长度可以利用KMP的next数组去快速获得,然后由于转移可能形成环的情况,所以无法直接DP,利用高斯消元去解方程组
代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef long long type; struct Frac { type a, b; Frac() {a = 0; b = 1;} Frac(type a, type b) {this->a = a; this->b = b; deal();} void init() {a = 0; b = 1;} type gcd(type a, type b) { while (b) { type tmp = a % b; a = b; b = tmp; } return a; } void deal() { type d = gcd(a, b); a /= d; b /= d; if (b < 0) { a = -a; b = -b; } } Frac operator + (Frac c) { Frac ans; ans.a = a * c.b + b * c.a; ans.b = b * c.b; ans.deal(); return ans; } Frac operator - (Frac c) { Frac ans; ans.a = a * c.b - b * c.a; ans.b = b * c.b; ans.deal(); return ans; } Frac operator * (Frac c) { Frac ans; ans.a = a * c.a; ans.b = b * c.b; ans.deal(); return ans; } Frac operator / (Frac c) { Frac ans; ans.a = a * c.b; ans.b = b * c.a; ans.deal(); return ans; } void operator += (Frac c) {*this = *this + c;} void operator += (type c) {*this = *this + Frac(c, 1);} void operator -= (Frac c) {*this = *this - c;} void operator *= (Frac c) {*this = *this * c;} void operator /= (Frac c) {*this = *this / c;} bool operator > (Frac c) {return a * c.b > b * c.a;} bool operator == (Frac c) { return a * c.b == b * c.a;} bool operator < (Frac c) {return !(*this < c && *this == c);} bool operator >= (Frac c) {return !(*this < c);} bool operator <= (Frac c) {return !(*this > c);} bool operator != (Frac c) {return !(*this == c);} bool operator != (type c) {return *this != Frac(c, 1);} void operator = (type c) {this->a = c; this->b = 1;} }; typedef long long ll; Frac A[15][15]; int t, m, n, next[15]; char str[15]; void getnext() { next[0] = next[1] = 0; int j = 0; for (int i = 2; i <= n; i++) { while (j && str[i] != str[j + 1]) j = next[j]; if (str[i] == str[j + 1]) j++; next[i] = j; } } void build() { for (int i = 0; i <= n; i++) for (int j = 0; j <= n + 1; j++) A[i][j].init(); getnext(); A[n][n] = 1; for (int i = 0; i < n; i++) { A[i][i] = 1; A[i][n + 1] = 1; for (int j = 0; j < m; j++) { if (str[i + 1] == j + 'A') A[i][i + 1] += Frac(-1, m); else { int tmp = i; int flag = 1; while (tmp) { tmp = next[tmp]; if (str[tmp + 1] == j + 'A') { flag = 0; A[i][tmp + 1] += Frac(-1, m); break; } } if (flag) A[i][0] += Frac(-1, m); } } } } ll gauss() { for (int i = 0; i <= n; i++) { int r; for (r = i; r <= n; r++) if (A[r][i] != 0) break; for (int j = i; j <= n + 1; j++) swap(A[i][j], A[r][j]); for (int j = n + 1; j > i; j--) A[i][j] /= A[i][i]; A[i][i] = 1; for (int j = 0; j <= n; j++) { if (i == j) continue; if (A[j][i] != 0) { for (int k = n + 1; k > i; k--) A[j][k] -= A[j][i] * A[i][k]; A[j][i] = 0; } } } return (A[0][n + 1] / A[0][0]).a; } int main() { int cas = 0; scanf("%d", &t); while (t--) { scanf("%d%s", &m, str + 1); n = strlen(str + 1); build(); printf("Case %d:\n", ++cas); printf("%lld\n", gauss()); if (t) printf("\n"); } return 0; }
UVA 1358 - Generator(dp+高斯消元+KMP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。