元音和辅音显然是独立的,我们考虑分开计算。记只用元音和辅音组成的单词数分别为 $ans_p$ 和 $ans_q$,则总答案为 $ans_p \times ans_q + ans_p + ans_q$。
考虑计算 $ans_p$,$ans_q$是类似的。枚举单词长度 $i$,显然有, \[ ans_p = \sum_{i=1}^{n}{(i+1)p^i} = \frac{ p \frac{1-p^n}{1-p} + p -(n+1)p^{n+1}}{1-p} \] 这个式子可以 $O(\log n)$,但问题是 $1-p$ 不一定有逆元,所以是行不通的。
由于没有逆元,我们希望递推计算答案。 记 $f(n) = \sum_{i=1}^{n}{(i+1)p^i}$,整个式子是不好递推的,我们把它拆开,用 $p^i$ 和 $ip^i$ 去凑它。我们有, \[ \left\{\begin{array}{l} f(i) = f(i-1) + (i+1)p^i = f(i-1) + ip^i + p^i\\ ip^i = p \times (i-1)p^{i-1} + p \times p^{i-1}\\p^i = p \times p^{i-1}\end{array}\right.\] 这样就可以构造矩阵了。 \[ \begin{bmatrix} f(i-1)\\ (i-1)p^{i-1}\\ p^{i-1} \end{bmatrix} \begin{bmatrix} 1 & p & 2p\\ 0 & p & p\\ 0 & 0 & p \end{bmatrix} = \begin{bmatrix} f(i)\\ ip^i\\ p^i \end{bmatrix} \] 时间复杂度$O(\log n)$。
题目1471 [SRM 377] 外星语言
9
评论
2023-01-03 09:00:51
|
|
题目3354 [USACO20 Feb Silver]Swapity Swapity Swap
8
评论
2022-12-20 16:11:06
|
|
考虑将答案转化为期望,最后乘上 $2^{n-1}$。 如果 $a_i$ 前是加号,有 $\frac{1}{2}$ 的概率,因此贡献为 $\frac{a_i}{2}$。 如果 $a_i$ 前是乘号,有 $\frac{1}{2}$ 的概率,贡献是 $\frac{a_i-1}{2}$ 乘以前 $i-1$ 个数的期望后缀乘积,这个可以递推算出来。 时间复杂度:$\mathcal O(n)$。
题目2752 [济南集训 2017] 数列运算
8
评论
2022-12-19 22:56:44
|
|
简要题解: 先手推一波式子: $$f(i,m)=a^{m-1}\times f(i,1)+\frac{a^{m-1}-1}{a-1}\times b$$ 再次展开,得: $$\begin{bmatrix}f(i,m) & 1\end{bmatrix}\times \begin{bmatrix}a^{m-1}\times c & 0\\a^{m-1}\times d+\frac{a^{m-1}-1}{a-1}\times b & 1\\\end{bmatrix}=\begin{bmatrix}f(i+1,m) & 1\end{bmatrix}$$ 高精度十进制快速幂即可。 注意特殊处理 $a=1$ 的情况。
题目1397 [NOI 2013]矩阵游戏
AAAAAAAAAAAAAAAAAAAA
9
评论
2022-12-13 17:51:30
|
|
显然的贪心思路:让被经过期望次数多的边的编号尽量小。但是这题 $m$ 可能为 $10^5$ 级别,不能对边进行求解。 考虑求出每个点的期望经过次数,设其为 $f_i$,令点 $i$ 的度数为 $deg_i$。 则有: $$f_1=(\sum\limits_{(1,v)\in E\land v\neq n} \frac{f_v}{deg_v})+1,f_i=\sum\limits_{(i,v)\in E\land v\neq n}\frac{f_v}{deg_v}(1\lt i\lt n)$$ $v\neq n$ 的原因是,一旦 $v=n$,就走到 $n$ 了,肯定不可能再走回 $i$。 因为有后效性,所以将其列成矩阵进行高斯消元求解。 则: $$\forall (u,v)\in E,g(u,v)=\frac{f_u}{deg_u}+\frac{f_v}{deg_v}$$ 其中 $g(u,v)$ 表示边 $(u,v)$ 被经过的期望次数。 注意特判 $u\neq n,v\neq n$,原因同上。 时间复杂度 $\mathcal O(n^3)$。
题目2477 [HNOI 2013]游走
AAAAAAAAAA
9
评论
2022-12-09 16:55:23
|
|
Pro1989 BD 题解搜不到题解啊,自己随便写一篇玩。 如果直接求亮灯数的期望 $E$,这是不好处理的,因为我们不可能把所有灯的亮暗同时放入到状态中。 不妨换一个角度,去分别考虑每个灯最终的状态。考虑计算坐标$(x,y,z)$的灯最终亮着的概率 $P_{x,y,z}$,那么它有 $P_{x,y,z}$ 的概率给答案贡献 $1$,即 $E=\sum{p_{x,y,z}}$。
接下来的问题是如何计算 $P_{x,y,z}$。 首先考虑任选 $A,B$ 能包含 $(x,y,z)$ 的概率(以下简记为 $P_{cr}$),不难得到 $P_{cr}=\frac{2x(n-x+1)-1}{n^2}\frac{2y(m-y+1)-1}{m^2}\frac{2z(p-z+1)-1}{p^2}$。
一种直接的想法是DP。设 $f_{i,x,y,z,0/1}$ 表示 $i$ 次操作后,$(x,y,z)$ 暗/亮的概率,转移显然: $f_{i,x,y,z,0/1}=P_{cr}f_{i-1,x,y,z,1/0}+(1-P_{cr})f_{i-1,x,y,z,0/1}$ 第一维可以滚,时间复杂度$O(nmpk)$,寄了。
仔细想想其实不用DP,一盏灯最终是亮的,那么它可能被操作 $1,3,5,...$ 次,即 $P_{x,y,z}=val(1)+val(3)+val(5)+...$,其中 $val(i)$ 表示恰好被操作 $i$ 次的概率。 $val(i)$ 怎么算?其实就是从 $k$ 次操作中选出 $i$ 个包含它,即 $val(i)=C^{i}_{k}P_{cr}^i(1-P_{cr})^{k-i}$。 整理一下,$P_{x,y,z}=C^{1}_{k}P_{cr}(1-P_{cr})^{k-1}+C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+...$ 经典二项式定理。 $[(1-P_{cr})+P_{cr}]^k=C^{0}_{k}(1-P_{cr})^{k}+C^{1}_{k}P_{cr}^1(1-P_{cr})^{k-1}+C^{2}_{k}P_{cr}^2(1-P_{cr})^{k-2}+C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+... (\alpha)$ $[(1-P_{cr})-P_{cr}]^k=C^{0}_{k}(1-P_{cr})^{k}-C^{1}_{k}P_{cr}^1(1-P_{cr})^{k-1}+C^{2}_{k}P_{cr}^2(1-P_{cr})^{k-2}-C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+... (\beta)$ 于是$P_{x,y,z}=\frac{\alpha-\beta}{2}=\frac{1-(1-2P_{cr})^k}{2}$ 这样就整完了。时间复杂度$O(nmp\log k)$,其中$\log k$为快速幂。 |