手机网站建设专家,有人知道网站怎么做吗,在广州学编程有名气的培训班,公司网页网站建设 ppt正题
题目链接:https://www.luogu.com.cn/problem/P3706 题目大意
给出 nnn 个长度为 mmm 的 H/TH/TH/T 串。
开始一个空序列#xff0c;每次随机在后面加一个 H/TH/TH/T #xff0c;求每个串第一次出现的概率。 1≤n,m≤3001\leq n,m\leq 3001≤n,m≤300 解题思路
数据范…正题
题目链接:https://www.luogu.com.cn/problem/P3706 题目大意
给出 nnn 个长度为 mmm 的 H/TH/TH/T 串。
开始一个空序列每次随机在后面加一个 H/TH/TH/T 求每个串第一次出现的概率。
1≤n,m≤3001\leq n,m\leq 3001≤n,m≤300 解题思路
数据范围显然不能在AC自动机上高斯消元所以得考虑别的方法。
考虑一个很妙的做法设一个状态NNN表示目前还没有匹配完成的串然后考虑串AHHTAHHTAHHT和串BTHHBTHHBTHH那么在NNN后面直接插入一个AAA的概率就是p(NA)p(N)×2−mp(NA)p(N)\times 2^{-m}p(NA)p(N)×2−m
但是考虑到有可能NNN先拼出了BBB然后再拼出AAA此时考虑BBB的后缀对应AAA前缀的有H,HHH,HHH,HH。那么就有 p(N)×2−mp(NA)p(A)p(B)×2−2p(B)×2−1p(N)\times 2^{-m}p(NA)p(A)p(B)\times 2^{-2}p(B)\times 2^{-1}p(N)×2−mp(NA)p(A)p(B)×2−2p(B)×2−1
这样不难发现对于别的串如果它的一些后缀是这个串的前缀那么就会产生一些概率用字符串hashhashhash匹配即可。
然后会发现还是少了一个方程最后一个就是所有串的概率和为111就好了。
这样就有n1n1n1个方程了。
时间复杂度O(n2mn3)O(n^2mn^3)O(n2mn3) code
#includecstdio
#includecstring
#includealgorithm
#define ull unsigned long long
using namespace std;
const int N310;
const ull g131;
int n,m;
double a[N][N],b[N],pw[N];
ull h[N][N],p[N];char s[N];
ull geth(int x,int l,int r)
{return h[x][r]-h[x][l-1]*p[r-l1];}
void Gauss(int n){for(int i1;in;i){int zi;for(int ji1;jn;j)if(a[j][i]a[z][i])zi;swap(a[i],a[z]);double xa[i][i];b[i]/x;for(int ji;jn;j)a[i][j]/x;for(int ji1;jn;j){double rate-a[j][i];for(int ki;kn;k)a[j][k]rate*a[i][k];b[j]rate*b[i];}}for(int in;i1;i--){for(int j1;ji;j){b[j]-a[j][i]*b[i];a[j][i]0;}}return;
}
int main()
{scanf(%d%d,n,m);p[0]1;pw[0]1;for(int i1;im;i)pw[i]pw[i-1]*0.5,p[i]p[i-1]*g;for(int i1;in;i){scanf(%s,s1);for(int j1;jm;j)h[i][j]h[i][j-1]*gs[j];}for(int i1;in;i)for(int j1;jn;j)for(int k1;km;k)if(geth(i,1,k)geth(j,m-k1,m))a[i][j]pw[m-k];for(int i1;in;i)a[i][n1]-pw[m],a[n1][i]1;b[n1]1;Gauss(n1);for(int i1;in;i)printf(%.12lf\n,b[i]);return 0;
}
