【BZOJ1444】[Jsoi2009]有趣的游戏 AC自动机+概率DP+矩阵乘法

2021-07-20 20:13

阅读:604

标签:i++   inpu   cpp   log   自乘   out   数据   name   注意   

【BZOJ1444】[Jsoi2009]有趣的游戏

Description

技术分享

Input

技术分享

注意 是0

Output

技术分享

Sample Input

技术分享

Sample Output

技术分享

HINT

技术分享 30%的数据保证, n ≤ 2. 50%的数据保证, n ≤ 5. 100%的数据保证, n , l, m≤ 10.

题解:本题的做法真的很多啊,概率DP,期望DP,当然还有矩乘黑科技~

就是先跑AC自动机,弄出转移矩阵,然后自乘50次就行了。

#include 
#include 
#include 
#include 
using namespace std;
int n,l,m,tot;
double c[30],ans[20];
queue q;
struct node
{
	int ch[30],fail,dan;
}p[110];
char str[20];
struct M
{
	double v[110][110];
	M (){memset(v,0,sizeof(v));}
	double* operator [](int x)	{return v[x];}
	M operator * (M a) const
	{
		M c;
		for(int i=1;i

【BZOJ1444】[Jsoi2009]有趣的游戏 AC自动机+概率DP+矩阵乘法

标签:i++   inpu   cpp   log   自乘   out   数据   name   注意   

原文地址:http://www.cnblogs.com/CQzhangyu/p/7054861.html


评论


亲,登录后才可以留言!