卧薪尝胆,厚积薄发。
SDOI2017 硬币游戏
Date: Sun Mar 10 20:31:03 CST 2019
In Category:
NoCategory
Description:
$N$
个给定的、长度为
$M$
的模式串。逐位随机生成
$01$
串,问每个模式串被首先生成的概率。
$1\leqslant N,M\leqslant 300$
Solution1:
和
$CTSC2006$
歌唱王国类似,设
$F_k(x)$
表示字符串在
$i$
处以第
$k$
个串结尾并且之前没有出现过其他模式串的串的个数的生成函数,那么我们要求的就是
$F_i(1/\Sigma)=F_i(0.5)$
。
设
$G(x)$
表示最后在第
$i$
个位置出现了模式串,但是不一定是第一次出现的方案数的生成函数。
$$
G(x)=\sum_{i\geqslant 0}2^ix^i\times x^m
$$
含义就是前
$i$
个可以是任意字符,最后
$m$
个确定,那么有:
$$
G=\frac{x^m}{1-2x}
$$
类似歌唱王国,设:
$$
P_{a,b}=\sum_{i=1}^m[suf_a[i]=pre_b[i]]x^i
$$
最后一个串和之前不相交的结果是
$F_jG$
,相交的结果是
$F_jP_{j,i}$
那么就会有:
$$
F_i=G-\sum_{j=1}^nF_j(G+P_{j,i})
$$
$$
\begin{align}
F_i&=G-\sum_{j=1}^nF_j(G+P_{j,i})\\
F_i(x)&=\frac{x^m}{1-2x}-\sum_{j=1}^nF_j(x)(\frac{x^m}{1-2x}+P_{j,i}(x))\\
\end{align}
$$
我们应该把
$x=0.5$
代入,但是不能直接代入,因为分母是
$0$
,所以我们先把分母乘上去然后再求导,据说这样再代入计算出的答案就是对的了,证明好像需要洛必达法则,不会:
$$
\begin{align}
(1-2x)F_i(x)&=x^m-\sum_{j=1}^nF_j(x)x^m-(1-2x)\sum_{j=1}^nF_j(x)P_{j,i}(x)\\
(1-2x)F'_i(x)-2F_i(x)&=mx^{m-1}-mx^{m-1}\sum_{j=1}^nF_j(x)-\sum_{j=1}^nx^mF_j'(x)+2\sum_{j=1}^nF_j(x)P_{j,i}(x)-(1-2x)\Bigl(\sum_{j=1}^nF_j(x)P_{j,i}(x)\Bigr)'\\
-2F_i(\frac12)&=m\frac1{2^{m-1}}-m\frac1{2^{m-1}}\sum_{j=1}^nF_j(\frac12)-\sum_{j=1}^n\frac1{2^m}F'_j(\frac12)+2\sum_{j=1}^nF_j(\frac12)P_{j,i}(\frac12)\\
F_i(\frac12)&=-m\frac1{2^m}+m\frac1{2^m}\sum_{j=1}^nF_j(\frac12)+\sum_{j=1}^n\frac1{2^{m+1}}F'_j(\frac12)-\sum_{j=1}^nF_j(\frac12)P_{j,i}(\frac12)\\
\end{align}
$$
于是设
$x_i=F_i(\frac12)$
,那么我们就可以列出
$n$
个方程,再加一个方程
$\sum x_i=1$
就可以高斯消元了。
Solution2:
考虑直接套用歌唱王国那题的做法:
$F_i$
表示第
$i$
个序列成功的方案数,
$G$
表示未成功的方案数,那么依然有:
$$
\sum_{i=1}^nF_i(x)+G(x)=xG(x)+1\\
G(x)(\frac 12x)^m=\sum_{j=1}^n\sum_{k=1}^ma_{i,j,k}F_j(x)(\frac 12x)^{m-k}
$$
$a_{i,j,k}$
表示第
$i$
个序列的前
$k$
位是否等于第
$j$
个序列的后
$k$
位。
然后还是对第一个式子求导:
$$
\begin{align}
\sum_{i=1}^nF'_i(x)+G'(x)&=xG'(x)+x'G(x)\\
\sum_{i=1}^nF'_i(1)&=G(1)
\end{align}
$$
然后:
$$
G(1)=\sum_{j=1}^n\sum_{k=1}^ma_{i,j,k}F_j(1)2^k
$$
于是我们可以列出
$n+1$
个方程(最后一个是
$\sum F_i=1$
)于是就可以高斯消元了。
Code:
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
int n,m;
#define MAXN 310
int s[MAXN][MAXN];
#define BASE 19260817
#define MOD 1000000007
int power[MAXN];
double pow2[MAXN];
int getc()
{
register char c = getchar();
while(c != 'H' && c != 'T')c = getchar();
return (c == 'H' ? 0 : 1);
}
struct hash
{
int v[MAXN];
int get(int l,int r)
{
return (v[r] - 1ll * v[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;
}
}h[MAXN];
int a[MAXN][MAXN][MAXN];
double g[MAXN][MAXN];
double b[MAXN];
double res[MAXN];
int main()
{
scanf("%d%d",&n,&m);
power[0] = 1;for(int i = 1;i <= m;++i)power[i] = 1ll * power[i - 1] * BASE % MOD;
pow2[0] = 1;for(int i = 1;i <= m;++i)pow2[i] = pow2[i - 1] * 2;
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
s[i][j] = getc();
h[i].v[j] = (1ll * h[i].v[j - 1] * BASE % MOD + s[i][j]) % MOD;
}
}
for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)for(int k = 1;k <= m;++k)
a[i][j][k] = h[i].get(1,k) == h[j].get(m - k + 1,m);
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j)for(int k = 1;k <= m;++k)g[i][j] += a[i][j][k] * pow2[k];
g[i][n + 1] = -1;
}
for(int i = 1;i <= n;++i)g[n + 1][i] = 1;
b[n + 1] = 1;
for(int i = 1;i <= n + 1;++i)
{
for(int j = i;j <= n + 1;++j)
{
if(fabs(g[i][j]) > 1e-8)
{
swap(g[i],g[j]);swap(b[i],b[j]);
break;
}
}
for(int j = i + 1;j <= n + 1;++j)
{
double delta = g[j][i] / g[i][i];
for(int k = i;k <= n + 1;++k)
{
g[j][k] = g[j][k] - delta * g[i][k];
}
b[j] = b[j] - delta * b[i];
}
}
for(int i = n + 1;i >= 1;--i)
{
res[i] = b[i] / g[i][i];
for(int j = i - 1;j >= 1;--j)
{
b[j] -= g[j][i] * res[i];
}
}
for(int i = 1;i <= n;++i)printf("%.10lf\n",res[i]);
return 0;
}
In tag:
数学-组合数学-生成函数 数学-线性代数-高斯消元
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡