My Blogs
[ARC170E] BDFS
唐完了。
翻译一下题目在说什么：有两个指针 $L,R$，一开始均为 $0$。一开始有一个 $opt=0$，发生以下事件 $n-1$ 次：
-
如果 $opt=0$，则 $L\leftarrow L +1$，否则。$R\leftarrow R +1$。
-
$opt$ 有 $P$ 的概率保持不变，有 $1-P$ 的概率变成 $1-opt$。
这样最后 $L+R$ 一定等于 $n-1$，并且其贡献为 $\frac{L(L+1)}{2}+\frac{R(R+1)}{2}$。用一个序列记录每一步扩展时的 $opt$，设 $opt_i$ 表示第 $i$ 次扩展时 $opt$ 的取值。对于一个序列，一个 相邻颜色相同对 会对概率乘一个 $p$，不同会乘一个 $1-p$。
根据期望的线性性，把贡献拆开，看成是任意选取两个颜色相同的 $i,j$，其中 $i\leq j$ 的方案数。计算答案时先枚举序列中的 $i,j$。枚举 $opt$ 在 $[i,j]$ 中间变化了 $k$ 次，则出现概率即为 $\sum_k[2\vert k]\binom{i-j}{k}p^{i-j-k}(1-p)^k$。
看成生成函数形式： $ \sum_k[2\vert k][x^k] (1+(1-p)x)^{i-j} $，对 $F(x)$ 偶数次项系数求和等价于计算 $\frac{F(1)+F(-1)}{2}$，因为奇数项的贡献相反，而偶数项相同。整理得 $i,j$ 颜色相同的概率就是 $1+(2p-1)^{i-j}$。
最终答案就是 $\sum_{1\leq i\leq j< n}1+(2p-1)^{j-i}$。对其化简：
\[\begin{aligned} &\sum_{1\leq i\leq j< n}1+(2p-1)^{j-i}\\ =&\frac{n(n-1)}{2}+\sum_{1\leq i\leq j< n}(2p-1)^{j-i}\\ =&\frac{n(n-1)}{2}+\sum_{0\leq i\leq n-2}(n-1-i)(2p-1)^{i}\\ =&\frac{n(n-1)}{2}+(n-1)\sum_{0\leq i\leq n-2}(2p-1)^{i}-\sum_{0\leq i\leq n-2}i(2p-1)^{i}\\ \end{aligned}\]第二部分是等比数列求和，第三部分也可以用类似等比数列求和的过程求出，总复杂度 $\mathcal O(T\log n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n,P;
inline void mian()
{
read(n,P);
--n;
Mmul(P,power(100,MOD-2));
P=(2*P-1)%MOD;
int ans=Cmul(n%MOD,n%MOD+1,inv2);
int tmp=Cmul(Cdel(power(P,n),1),power(Cdel(P,1),MOD-2));
Madd(ans,Cmul(n%MOD,tmp));
int val=Cdel(Cmul((n-1)%MOD,power(P,n))+1,tmp);
Mdel(ans,Cmul(val,power(P-1,MOD-2)));
write(Cmul(ans,inv2),'\n');
}
inline void Mian()
{
int T=1;
read(T);
while(T--)mian();
}