bzoj1444[Jsoi2009]有趣的游戏[AC自动机]

题面

我要向师父学习善待每一只数据结构

考虑成环，那么高斯消元

然鹅这道题太小了所以直接转移矩阵自乘就好啦

终点不向外连边有一条向自己的，概率为一的自环来作为结尾

对于其他店若有边\((u -> v) = p\) 那么mat[u][v] += p



#include <cmath>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <complex>

#include <ctime>

#include <vector>

#include <queue>

#include <bitset>

#define mp(x, y) make_pair(x, y)

using namespace std;

const int N = 15;

const int M = 105;

int n, m, len, sz, en[N];

double p[N];

struct Matrix{

	double w[M][M];

	void clear(){

		for(int i = 0; i <= sz; ++i)

		     for(int j = 0; j <= sz; ++j)

		         w[i][j] = 0;

	}

	void print(){

		printf("--------------------\n");

		for(int i = 0; i <= sz; ++i){

		     for(int j = 0; j <= sz; ++j)

		         printf("%.2lf ", w[i][j]);

			printf("\n");

		}

		printf("--------------------\n");

	}

	friend Matrix operator *(const Matrix x, const Matrix y){

		Matrix z; z.clear();

		for(int i = 0; i <= sz; ++i)

		    for(int j = 0; j <= sz; ++j)

		        for(int k = 0; k <= sz; ++k)

		            z.w[i][j] += x.w[i][k] * y.w[k][j];

	//	z.print();

	    return z;

	}

}mat, res;

struct AC{

	int ch[M][N], f[M];

	bool flag[M];

	queue<int> que;

	void ins(char* str, int id){

		int now = 0;

		for(int i = 1, cc; i <= len; ++i){

			cc = str[i] - 'A';

			if(!ch[now][cc]) ch[now][cc] = ++sz;

			now = ch[now][cc];

		}

		en[id] = now, flag[now] = 1;

	}

	void build(){

		int now = 0;

		for(int i = 0; i < m; ++i) if(ch[0][i]) que.push(ch[0][i]);

		while(!que.empty()){

			int fro = que.front(); que.pop();

			for(int i = 0; i < m; ++i){

				if(ch[fro][i]) f[ch[fro][i]] = ch[f[fro]][i], que.push(ch[fro][i]);//!!

				else ch[fro][i] = ch[f[fro]][i];

			}

		}

		mat.clear();

		for(int i = 0; i <= sz; ++i){

			if(flag[i]){

				mat.w[i][i] = 1; continue;

			}

		    for(int j = 0; j < m; ++j){

		    	mat.w[i][ch[i][j]] += p[j];

		    }

		}

	}

}ac;

int main(){

    scanf("%d%d%d", &n, &len, &m);

    for(int i = 0; i < m; ++i){

    	double x, y; scanf("%lf%lf", &x, &y);

    	p[i] = x / y;

    }

    char str[N];

    for(int i = 1; i <= n; ++i){

    	scanf("%s", str + 1);

    	ac.ins(str, i);

    }

    ac.build();

    for(int i = 1; i <= 100; ++i) mat = mat * mat;

    //转移矩阵自乘 得到来自0的解

	for(int i = 1; i <= n; ++i) printf("%.2lf\n", mat.w[0][en[i]]);

    return 0;

}

巴特西

bzoj1444[Jsoi2009]有趣的游戏[AC自动机]

题面

最新文章

热门文章