bzoj 1444 AC自动机 + 矩阵乘法 | 高斯消元
2024-08-24 20:00:37
恶补了一下AC自动机,花了一天时间终于全部搞明白了。
思路:将每个人的串加入AC自动机,在AC自动机生成的状态图上建边,注意单词末尾的节点只能转移到自己概率为1,
然后将矩阵自乘几十次后误差就很小了, 或者可以高斯消元搞出精确解。
#include<bits/stdc++.h>
#define LL long long
#define ll long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>
#define y1 skldjfskldjg
#define y2 skldfjsklejg using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ; int n, l, m, pos[];
double pro[];
char s[]; struct Matrix {
int r, c;
double a[][];
Matrix(int r = , int c = ) {
this->r = r;
this->c = c;
memset(a, , sizeof(a));
} Matrix operator * (const Matrix &B) const {
Matrix C(r, c);
for(int i = ; i < r; i++)
for(int j = ; j < c; j++)
for(int k = ; k < r; k++)
C.a[i][j] += a[i][k] * B.a[k][j];
return C;
}
}; struct Ac {
int val[N], ch[N][], f[N], last[N], cnt, SZ; void init(int SZ = ) {
cnt = ; this->SZ = SZ;
for(int c = ; c < SZ; c++) ch[][c] = ;
} int getId(char c) {
return c - 'A';
} int newNode() {
cnt++;
memset(ch[cnt], , sizeof(ch[cnt]));
val[cnt] = f[cnt] = last[cnt] = ;
return cnt;
} void add(char *s, int &pos) {
int u = ;
for(int i = ; s[i]; i++) {
int c = getId(s[i]);
if(!ch[u][c]) ch[u][c] = newNode();
u = ch[u][c];
}
val[u]++;
pos = u;
} void build() {
queue<int> que;
f[] = ;
for(int c = ; c < SZ; c++) {
if(!ch[][c]) continue;
f[ch[][c]] = last[ch[][c]] = ;
que.push(ch[][c]);
}
while(!que.empty()) {
int u = que.front(); que.pop();
for(int c = ; c < SZ; c++) {
int v = ch[u][c];
if(!v) {
ch[u][c] = ch[f[u]][c];
continue;
} else {
que.push(v);
f[v] = ch[f[u]][c];
last[v] = val[f[v]] ? f[v] : last[f[v]];
}
}
}
} void buildMatrix(Matrix &A) {
for(int u = ; u <= cnt; u++) {
if(val[u]) A.a[u][u] = ;
else {
for(int c = ; c < m; c++) {
int v = ch[u][c];
A.a[u][v] += pro[c];
}
}
}
}
} ac; int main() {
scanf("%d%d%d", &n, &l, &m);
for(int i = ; i < m; i++) {
double p, q;
scanf("%lf%lf", &p, &q);
pro[i] = p / q;
} ac.init(m); for(int i = ; i <= n; i++) {
scanf("%s", s);
ac.add(s, pos[i]);
} ac.build();
Matrix A(ac.cnt + , ac.cnt + );
ac.buildMatrix(A); for(int i = ; i <= ; i++)
A = A * A; for(int i = ; i <= n; i++) printf("%.2f\n", A.a[][pos[i]]);
return ;
} /*
*/
最新文章
- spring和Hibernate整合
- TortoiseSVN客户端重新设置用户名和密码
- [CentOS] 指定命令别名:Alias &; 软链接生成命令 ln -s
- php使用技巧--之链接地址
- 那些好用的iOS开发工具
- Windows Phone 之下拉菜单ListPicker
- Android 通过Dom, Sax, Pull解析网络xml数据
- 中国内地、台湾、香港、澳门和国外DNS服务器地址列表
- JavaSE教程-04Java中循环语句for,while,do&#183;&#183;&#183;while-练习2
- SmartSql 入门
- netstat、ps、top 、kill 命令备忘
- [译]Ocelot - Big Picture
- leetcode — simplify-path
- 多端统一框架尝试--Taro
- 将本地的mongodb迁移到阿里云
- POJ2392 Space Elevator
- Django的模板继承
- python-一个小爬虫,爬取图片
- 第 0 课 Golang环境搭建
- python基础之反射、面向对象进阶