OI - Do you like query problems?(AtCoder) | Lucky_Glass's Blog
0%

OI - Do you like query problems?(AtCoder)

还差很多


# 题面

有一个长度为 $n$ 的数列 $\{a_1,a_2,\dots,a_n\}$ 和一个整数 $b$,初始 $a_i=0,b=0$,$a_i$ 值域为 $[0,m-1]$。进行 $Q$ 次操作,每次操作是下列所有操作中的一种:

  • A l r v:对 $i\in[l,r]$,$a_i\leftarrow\max\{a_i,v\}$,这种操作一共包含 $m\times \frac{n(n+1)}{2}$ 种;
  • B l r v:对 $i\in[l,r]$,$a_i\leftarrow\min\{a_i,v\}$,这种操作一共包含 $m\times \frac{n(n+1)}{2}$ 种;
  • C l r:$b\leftarrow b+\sum_{i=l}^ra_i$,这种操作一共包含 $\frac{n(n+1)}2$ 种。

求 $Q$ 次操作后 $b$ 的期望(原题是求所有方案的 $b$ 之和,本质一样……)。

$1\le n,m,Q\le2\times 10^5$


# 解析

这是一道利用期望线性性分拆贡献的好题:),具体分拆贡献分为两步:

(Ⅰ)将 $\mathbf{E(b)}$ 分拆为每一次操作对 $\mathbf b$ 的贡献。

由题意易知只有 C操作 会对 $b$ 有贡献。若第 $i$ 次操作是 C 操作,设其对 $b$ 的贡献为 $ans_i$。一共有 $(2m+1)\binom n2$ 种操作,而 C 操作有 $\binom n2$ 种,于是某一次操作是 C 操作的概率是 $\frac 1{2m+1}$。然后可以写出下面的式子:

考虑怎么计算 $E(ans_j)$。

Tab. 记 $a_{i,j}$ 表示数字 $a_i$ 在 $j$ 次操作后的值。

(Ⅱ)将 $\mathbf{E(ans_j)}$ 分拆为每个 $\mathbf{E(a_{i,j})}$ 的贡献。

某次操作区间包含 $a_i$ 的概率为 $\frac{i(n-i+1)}{\binom n2}$,则

而对于 $E(a_{i,j})$,要利用到将离散期望用概率表达的技巧:

为了方便计算上式的概率,我们定义一次操作对 $a_i$ 有效,当且仅当:

  • 是 A/B 操作;
  • 操作区间包含 $i$;
  • 如果是 A(max) 操作,则要求 $v\ge a_i$;如果是 B(min) 操作,则要求 $v< a_i$。

那么可以推得某一次操作对 $a_i$ 有效的概率为 $H_i=\frac{i(n-i+1)}{\binom n2}\cdot\frac{2m}{2m+1}\cdot\frac{a_i+(m-a_i-1)}{m}$,发现概率与 $a_i$ 无关。

那么什么时候会有 $a_{i,j}>k$?当且仅当最后一次有效操作的 $v$ 有 $v>k$。所以 $P(a_{i,j}>k)$ 可以这样计算:

  • 在前 $(j-1)$ 次操作中(第 $j$ 次是 C 操作,一定无效)存在有效操作:$[1-(1-H_i)^{j-1}]$(即从所有方案中减去 $j-1$ 次操作都无效的方案);
  • 最后一次有效操作 $v>k$:$\frac{m-k-1}m$。

所以 $P(a_{i,j}>k)=\frac{m-k-1}m[1-(1-H_i)^{j-1}]$

综上

最后

后面对 $1-(1-H_i)^{j-1}$ 的式子求和就用等比数列,可以做到 $O(\log Q)$,于是总复杂度 $O(n\log Q)$。


# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MOD=998244353;
#define ci const int &

inline int Add(ci a,ci b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return 1ll*a*b%MOD;}
inline int Pow(ci a,ci b){return b? Mul(Pow(Mul(a,a),b>>1),(b&1)? a:1):1;}

int n,m,Q;

//p^0+p^1+...+p^(t-1)
int loca(int varp,int vart){return Mul(Sub(Pow(varp,vart),1),Pow(Sub(varp,1),MOD-2));}
int main(){
scanf("%d%d%d",&n,&m,&Q);
int var1=Pow(Mul(n,n+1),MOD-2),var2=Pow(2*m+1,MOD-2),var3=Mul(Sub(m,1),Pow(2,MOD-2)),ans=0;
for(int i=1;i<=n;i++){
int varq=Mul(Mul(i,n-i+1),Mul(var1,var2)),varp=Mul(Mul(Mul(m,i),n-i+1),Mul(var1,var2));
varp=Mul(varp,2),varq=Mul(varq,2);
int sum=Sub(Q,loca(Sub(1,varp),Q));
ans=Add(ans,Mul(sum,Mul(var3,varq)));
}
int all=Pow(Mul(Mul(n,n+1),Mul(Pow(2,MOD-2),2*m+1)),Q);
// printf("? %d\n",all);
printf("%d\n",Mul(ans,all));
return 0;
}

THE END

Thanks for reading!

Linked 何日重到苏澜桥-Bilibili