【luogu CF618G】Combining Slimes(矩阵乘法)(DP)
Combining Slimes
题目链接:luogu CF618G
题目大意
有一个长度为 n 的栈,如果栈顶两个值都是 x 就会合并成 x+1,一开始没有东西。
你有 p 的概率放进去一个 1,1-p 的概率放入 2,问你当栈被放满的时候,你的期望分数。
分数是栈里所有值的和。
思路
考虑统计每个位置的数的贡献。
由于某个位置的数会因为合并改变,考虑先搞点简单的,某个位置出现过:
a
i
,
j
a_{i,j}
ai,j 为用了
i
i
i 个位置,最左边是
j
j
j 的概率:
初始:
a
i
,
1
=
p
,
a
i
,
2
=
1
−
p
a_{i,1}=p,a_{i,2}=1-p
ai,1=p,ai,2=1−p
转移:
a
i
,
j
=
a
i
,
j
−
1
a
i
−
1
,
j
−
1
a_{i,j}=a_{i,j-1}a_{i-1,j-1}
ai,j=ai,j−1ai−1,j−1(就是后面的两个位置都是
j
−
1
j-1
j−1,合并成
j
j
j)
发现
i
>
1
i>1
i>1 的时候
a
i
,
1
,
a
i
,
2
a_{i,1},a_{i,2}
ai,1,ai,2 又要初始又要转移,那就特判一下都加上。
那我们要的不是出现过,而是它不会被合并掉,最后留了下来。
A
i
,
j
A_{i,j}
Ai,j 为用了
i
i
i 个位置,最左边是
j
j
j 而且不会被合并掉的概率:
初始化:
A
1
,
1
=
p
,
A
1
,
2
=
1
−
p
A_{1,1}=p,A_{1,2}=1-p
A1,1=p,A1,2=1−p
A
i
,
j
=
a
i
,
j
(
1
−
a
i
−
1
,
j
)
A_{i,j}=a_{i,j}(1-a_{i-1,j})
Ai,j=ai,j(1−ai−1,j)
那我们就可以试着算算期望了:
f
i
,
j
f_{i,j}
fi,j 为最后序列右边
i
i
i 位最左边是
j
j
j 的情况下,这
i
i
i 位的期望和。
那就直接枚举右边
i
−
1
i-1
i−1 位的,考虑一下范围。
不难想想,只有两种可能,要么是你自己是
1
1
1,它不是
1
1
1,要么它就比你小。
1
1
1 那个显然,如果你不是
1
1
1,它比你打一定要从至少
2
2
2 往上一步一步加,那
2
2
2 到它那个数之间的数都要经历过。
那到你那个数的时候就合并了啊!
然后发现
2
2
2 这个好像很特别,似乎要再 DP 一下:
b
i
,
j
b_{i,j}
bi,j 为长度为
i
i
i 的,第一次放进来的是
2
2
2,最左边是
j
j
j 的概率:
初始化:
b
i
,
2
=
1
−
p
b_{i,2}=1-p
bi,2=1−p
b
i
,
j
=
b
i
,
j
−
1
a
i
−
1
,
j
−
1
b_{i,j}=b_{i,j-1}a_{i-1,j-1}
bi,j=bi,j−1ai−1,j−1
同样的道理,我们也要求不变的:
B
i
,
j
B_{i,j}
Bi,j 为长度为
i
i
i,第一次放进来是
2
2
2,最左边是
j
j
j 而且不会被合并的概率:
初始化:
B
1
,
2
=
1
−
p
B_{1,2}=1-p
B1,2=1−p
B
i
,
j
=
b
i
,
j
(
1
−
a
i
−
1
,
j
)
B_{i,j}=b_{i,j}(1-a_{i-1,j})
Bi,j=bi,j(1−ai−1,j)
这些都弄好之后,我们正式开始搞
f
f
f 的转移:
f
i
,
j
=
j
+
∑
k
=
2
n
f
i
−
1
,
k
B
i
−
1
,
k
∑
k
=
2
m
B
i
−
1
,
k
(
j
=
1
)
f_{i,j}=j+\frac{\sum\limits_{k=2}^{n}f_{i-1,k}B_{i-1,k}}{\sum\limits_{k=2}^mB_{i-1,k}}(j=1)
fi,j=j+k=2∑mBi−1,kk=2∑nfi−1,kBi−1,k(j=1)
f
i
,
j
=
j
+
∑
k
=
1
j
−
1
f
i
−
1
,
k
A
i
−
1
,
k
∑
k
=
1
j
−
1
A
i
−
1
,
k
(
j
≠
1
)
f_{i,j}=j+\frac{\sum\limits_{k=1}^{j-1}f_{i-1,k}A_{i-1,k}}{\sum\limits_{k=1}^{j-1}A_{i-1,k}}(j\neq 1)
fi,j=j+k=1∑j−1Ai−1,kk=1∑j−1fi−1,kAi−1,k(j=1)
那我们就可以转移啦!
但是 n n n 很大,那你这个是 n 2 + n m n^2+nm n2+nm 的啊。
发现一个事情,你会觉得它一直没有
1
1
1 接着
2
2
2 的情况其实会很少。
而且你要注意到你凑出
x
x
x 你至少需要
2
x
−
2
2^{x-2}
2x−2 次。
那比如一个
50
50
50,那不出现
1
,
2
1,2
1,2 的概率就是
(
1
−
p
(
1
−
p
)
)
2
50
(1-p(1-p))^{2^{50}}
(1−p(1−p))250,只要下面不是
1
1
1 基本上就宣告约等于
0
0
0 了。
那合并的概率也就是
0
0
0。
也就是说,我们设
m
=
50
m=50
m=50,那
j
⩾
m
j\geqslant m
j⩾m 的时候,我们可以认为
A
i
,
j
=
0
,
B
i
,
j
=
0
A_{i,j}=0,B_{i,j}=0
Ai,j=0,Bi,j=0。
然后发现
i
,
j
i,j
i,j 太大的
i
i
i 也不好搞啊,但是你看看那个式子:
A
i
,
j
=
a
i
,
j
(
1
−
a
i
−
1
,
j
)
A_{i,j}=a_{i,j}(1-a_{i-1,j})
Ai,j=ai,j(1−ai−1,j),
B
i
,
j
B_{i,j}
Bi,j 也差不多。
那
j
j
j 很大的时候,
a
i
−
1
,
j
,
a
i
,
j
a_{i-1,j},a_{i,j}
ai−1,j,ai,j 都很小,那
A
i
,
j
A_{i,j}
Ai,j 不也很小,那就
0
0
0 咯,直接忽略,所以也只用看到
m
m
m。
(毕竟这题是有精度要求的,不是取模那些)
那再看式子:
f
i
,
j
=
j
+
∑
k
=
2
min
(
n
,
m
)
f
i
−
1
,
k
B
min
(
i
−
1
,
m
)
,
k
∑
k
=
2
min
(
n
,
m
)
B
min
(
i
−
1
,
m
)
,
k
(
j
=
1
)
f_{i,j}=j+\frac{\sum\limits_{k=2}^{\min(n,m)}f_{i-1,k}B_{\min(i-1,m),k}}{\sum\limits_{k=2}^{\min(n,m)}B_{\min(i-1,m),k}}(j=1)
fi,j=j+k=2∑min(n,m)Bmin(i−1,m),kk=2∑min(n,m)fi−1,kBmin(i−1,m),k(j=1)
f
i
,
j
=
j
+
∑
k
=
1
min
(
j
−
1
,
m
)
f
i
−
1
,
k
A
min
(
i
−
1
,
m
)
,
k
∑
k
=
1
min
(
j
−
1
,
m
)
A
min
(
i
−
1
,
m
)
,
k
(
j
≠
1
)
f_{i,j}=j+\frac{\sum\limits_{k=1}^{\min(j-1,m)}f_{i-1,k}A_{\min(i-1,m),k}}{\sum\limits_{k=1}^{\min(j-1,m)}A_{\min(i-1,m),k}}(j\neq 1)
fi,j=j+k=1∑min(j−1,m)Amin(i−1,m),kk=1∑min(j−1,m)fi−1,kAmin(i−1,m),k(j=1)
然后我们如果把
⩽
m
\leqslant m
⩽m 的单独暴力处理,然后看
>
m
>m
>m 的部分:
f
i
,
j
=
j
+
∑
k
=
2
m
f
i
−
1
,
k
B
m
,
k
∑
k
=
2
m
B
m
,
k
(
j
=
1
)
f_{i,j}=j+\frac{\sum\limits_{k=2}^{m}f_{i-1,k}B_{m,k}}{\sum\limits_{k=2}^{m}B_{m,k}}(j=1)
fi,j=j+k=2∑mBm,kk=2∑mfi−1,kBm,k(j=1)
f
i
,
j
=
j
+
∑
k
=
1
m
f
i
−
1
,
k
A
m
,
k
∑
k
=
1
m
A
m
,
k
(
j
≠
1
)
f_{i,j}=j+\frac{\sum\limits_{k=1}^{m}f_{i-1,k}A_{m,k}}{\sum\limits_{k=1}^{m}A_{m,k}}(j\neq 1)
fi,j=j+k=1∑mAm,kk=1∑mfi−1,kAm,k(j=1)
怎么感觉,有点像那种递推的式子。
看看,会发现确实可以用
1
×
m
1\times m
1×m 的矩阵表示
f
i
f_i
fi。
然后转移矩阵因为
i
−
1
i-1
i−1 都给你变成了
j
j
j,所以是固定的。
那直接上矩阵快速幂就可以啦!
代码
#include<cstdio>
using namespace std;
const int N = 55;
int n, m;
double p, a[N][N], A[N][N], b[N][N], B[N][N], f[N][N];
struct matrix {
int n, m;
double a[N][N];
}A_, B_;
matrix operator *(matrix x, matrix y) {
matrix z; z.n = x.n; z.m = y.m;
for (int i = 0; i < z.n; i++)
for (int j = 0; j < z.m; j++)
z.a[i][j] = 0;
for (int k = 0; k < x.m; k++)
for (int i = 0; i < z.n; i++)
for (int j = 0; j < z.m; j++)
z.a[i][j] += x.a[i][k] * y.a[k][j];
return z;
}
matrix ksm(matrix x, int y) {
matrix z = x; y--;
while (y) {
if (y & 1) z = z * x;
x = x * x; y >>= 1;
}
return z;
}
int main() {
scanf("%d %lf", &n, &p);
p /= 1000000000; m = 50;
a[1][1] = p; a[1][2] = 1 - p;
for (int i = 2; i <= m; i++) {
a[i][1] = p; a[i][2] = 1 - p + a[i][1] * a[i - 1][1];
for (int j = 3; j <= m; j++)
a[i][j] = a[i][j - 1] * a[i - 1][j - 1];
}
A[1][1] = p; A[1][2] = 1 - p;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= m; j++)
A[i][j] = a[i][j] * (1 - a[i - 1][j]);
}
b[1][2] = 1 - p;
for (int i = 2; i <= m; i++) {
b[i][2] = 1 - p;
for (int j = 3; j <= m; j++)
b[i][j] = b[i][j - 1] * a[i - 1][j - 1];
}
B[1][2] = 1 - p;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= m; j++)
B[i][j] = b[i][j] * (1 - a[i - 1][j]);
}
f[1][1] = 1; f[1][2] = 2;
for (int i = 2; i <= m; i++) {
double sum = 0;
for (int k = 2; k <= m; k++) {
f[i][1] += f[i - 1][k] * B[i - 1][k]; sum += B[i - 1][k];
}
f[i][1] = f[i][1] / sum + 1;
for (int j = 2; j <= m; j++) {
sum = 0;
for (int k = 1; k < j; k++) {
f[i][j] += f[i - 1][k] * A[i - 1][k];
sum += A[i - 1][k];
}
f[i][j] = f[i][j] / sum + j;
}
}
if (n <= m) {
double ans = 0;
for (int i = 1; i <= m; i++)
ans += A[n][i] * f[n][i];
printf("%.10lf", ans); return 0;
}
A_.n = 1; A_.m = m + 1; A_.a[0][0] = 1;
for (int i = 1; i <= m; i++) A_.a[0][i] = f[m][i];
B_.n = m + 1; B_.m = m + 1; B_.a[0][0] = 1;
for (int i = 1; i <= m; i++) {
B_.a[0][i] = i; if (i == 1) continue; double sum = 0;
for (int j = 1; j < i; j++) sum += A[m][j];
for (int j = 1; j < i; j++) B_.a[j][i] = A[m][j] / sum;
}
double sum = 0;
for (int i = 2; i <= m; i++) sum += B[m][i];
for (int i = 2; i <= m; i++) B_.a[i][1] = B[m][i] / sum;
B_ = ksm(B_, n - m); A_ = A_ * B_;
double ans = 0;
for (int i = 1; i <= m; i++)
ans += A[m][i] * A_.a[0][i];
printf("%.10lf", ans); return 0;
return 0;
}
相关文章
- GNN-频域-2016:ChebNet【频谱图卷积】【切比雪夫多项式(ChebShev Polynomial)】【应用切比雪夫多项式加速特征矩阵求解】【GCN来源于对ChebNet的进一步简化与近似】
- Matlab实现二进制矩阵转换为十进制
- hdu 1559 最大子矩阵(DP)
- 【Python基础】二维数组 (也叫矩阵)取值 示例~~~
- (可不看)【矩阵分析】Jordan标准形的应用举例(扩展用,应该不考这类题。不是考这种解法吧,就当扩展知识了)
- LeetCode_BFS_中等_542.01 矩阵
- 数学问题之(矩阵快速幂)
- 外参矩阵转四元数,左右手坐标系转化1
- 考研路茫茫——单词情结 HDU - 2243 AC自动机 && 矩阵快速幂
- 006 逆矩阵的求法(矩阵初等行变换)
- 矩阵的复习回顾
- 瑞蓝RL-NDVM-A16网络视频解码器 视频上墙解决方案专家--数字视频解码矩阵
- 【luogu CF645E】Intellectual Inquiry(DP)(结论)(矩阵乘法)
- 【ybtoj高效进阶 21278】内需消费(线段树)(广义矩阵乘法)(DP)
- 【nowcoder 226979】矩阵学说(二维ST表)(二分)
- [LeetCode] 240. Search a 2D Matrix II 搜索一个二维矩阵 II