随笔题解 Pb. 4

2022 年 10 月 1 日 20：00 ~ 21：40，AHU 2021 届不知名 ACM 选手関原みや（化名）报名参加 AtCoder Beginner Contest 271。期间因大脑短路，A/D/E 题各 WA 1 发，C 题 WA 4 发，G 题本应做出却未能做出（F 题就算了，真不会），最终以 1075th 的坏成绩遗憾离世离场，Rating 倒扣 17 分。距今已过 34 分 24 秒，警钟长鸣。

来源：ABC271 G Access Counter

高桥君建立了一个网站，然后在上面放置了一个访问计数器。在这之后，高桥君和他的一个朋友青木君会频繁地访问这个网站。

给定一个长度为 $24$ 的字符串 $c_0c_1\cdots c_{23}$，且 $c_i\in\{\mathtt{T},\mathtt{A}\}$。在访问计数器被设置后的第 $n$ 个小时中（$n$ 从零开始计数），如果 $c_{n\bmod 24}=\mathtt{T}$，那么高桥君有 $X/100$ 的概率访问网站；如果 $c_{n\bmod 24}=\mathtt{A}$，那么青木君有 $Y/100$ 的概率访问网站。

如果访问计数器统计到的第 $N$ 次访问恰好是高桥君，高桥君会爆炸。因此试求第 $N$ 次访问恰好是青木君的概率。对 $998244353$ 取模。

$1\leqslant N\leqslant 10^{18}$，$1\leqslant X,Y\leqslant 99$，且 $X$ 和 $Y$ 都是整数。

$\mathtt{2s/1024MB}$。

这么一看相当直来直去的概率题。

令 $P(i,j)$ 表示第 $i$ 次访问的下一次是第 $j$ 次访问的概率。这里不考虑这次访问是谁。显然我们有

$$P(i,j)=\sum_{n\geqslant 0}\prod_{k=i+1}^{j-1}(1-p_k)\cdot p_j\cdot\left(\prod_{k=1}^n(1-p_k)\right)^n=\frac{\prod_{k=i+1}^{j-1}(1-p_k)\cdot p_j}{1-\prod_{k=1}^n(1-p_k)}$$

$Q_t(i)$ 表示第 $t$ 访问对应 $c_i$ 的概率。显然我们有

$$Q_1(i)=\prod_{k=1}^{i-1}(1-p_k)\cdot p_i$$ $$Q_t(i)=\sum_{j=0}^{23}Q_{t-1}(j)P(j,i)$$

注意到，如果我们能够把 $P(i,j)$ 和 $Q_t(i)$ 写成如下的矩阵形式的话

$$A_t=\begin{bmatrix} Q_t(0)\\ Q_t(1)\\ \vdots\\ Q_t(23)\\ \end{bmatrix} \quad F=\begin{bmatrix} P(0,0)&P(1,0)&\cdots&P(23,0)\\ P(0,1)&P(1,1)&\cdots&P(23,1)\\ \vdots&\vdots&\ddots&\vdots\\ P(0,23)&P(1,23)&\cdots&P(23,23)\\ \end{bmatrix}$$

上面那个关系式就可以简写成

$$A_t=A_{t-1}F=A_1F^{t-1}$$

即

$$A_N=A_1F^{N-1}$$

那么我们就可以在 $O(\log N)$ 的时间复杂度内计算出所有的 $Q_N(i)$。虽然严格上来讲这部分还会有一个高达 $24^3$ 的常数。

那么最终的答案就是

$$\sum_{i=0}^{23}[c_i=\mathtt{A}]Q_N(i)$$