2024.6.29

2024.6.29

T1

题面

给定一个序列 \(a\)，从中若干个数，第 \(i\) 个元素有 \(p_i\) 的概率被选中，每个元素是否被选中之间是相互独立的。如果 \(b\) 的异或和为 \(s\),称它的权值为 \(s^2\) ,求 \(b\) 的权值的期望。
答案对 \(10^9+7\) 取模。

题解

因为是异或操作，我们可以转到二进制下进行操作，有

\[\operatorname E(s^2)=\operatorname E((\sum_{i=0}^{30}s_i)^2)=\operatorname E(\sum_{i,j}s_is_j2^{i+j})=\sum_{i,j}2^{i+j}\operatorname E(s_is_j)=\sum_{i,j}2^{i+j}\operatorname P(s_i=1\land s_j=1) \]

现在将求期望变为了求概率，令 \(dp_{x,i,j,0/1,0/1}\) 表示考虑前 \(x\) 个数，第 \(i\) 和 \(j\) 为状态分别为 \(0/1,0/1\) 的概，\(令bi=a[x]二进制下第 i 位，bj=a[x] 二进制下第 j 位\\\)，则

\[dp_{x,i,j,\alpha,\beta}=dp_{x-1,i,j,\alpha,\beta}\times (1-p_x)+dp_{x-1,i,j,\alpha \oplus bi,\beta\oplus bj}\times p_x \]

最后 \(\operatorname P(s_i=1\land s_j=1)=dp_{n,i,j,1,1}\)，可得答案。

复杂度 \(\mathcal O(n\log^2n)\)

方法

• 找到01变量，转期望为概率。

• 二进制下考虑

T2

题面

给定\(n,m\),对于每个\(1≤k≤m\),计数满足以下条件的01串数量：
1.长度为\(n\)，且恰有\(m\)个\(1\)和\(n−m\)个\(0\)
2.最长的\(1\)连续段长度恰好为\(k\)
注意\(m≠0\),因此最长的\(1\)连续段长度不可能是\(0\)。
答案对 \(10^9+7\) 取模。

题解

考虑容斥，利用\(等于=小于等于-小于\)的思路，转化为长度 \(\le k\)，进而转化为长度 \(>k\)。我们可以再\(k+1\) 个 \(1\) 后面添一个 \(0\) 表示一段的结束

令 \(S(n,t,k,m)=(-1)^t{n-tk\choose t}{n-t(k+1)\choose m-tk}\)

假设当前有 \(t\) 段不满足，带容斥系数方案数为 \(L(k,t)=S(n,t,k+1,m)-S(n-k-1,t-1,k+1,m-k-1)\)

因为还要考虑最后一个段后面不用加 \(0\) 需要将方案数加上，但这里是有容斥系数的加上，所以为减。

令为 \(A(k)=\sum_{t=0}^{\min((n-k-1)/(k+1)+1,m/(k+1)}L(k,t)\)，这是长度 \(\le k\) 的方案，最终答案为

\(A(k)-A(k-1)\)

复杂度 \(\mathcal O(n\log n)\)

方法

• slime段模型容斥

T3

题面

在石头剪刀布中，一共有三种手势 \(R(Rock),P(Paper),S(Scissors)\):

其中 \(R\)能赢 \(S,S\) 能赢 \(P,P\) 能赢 \(R\)。

现在，我们定义 \(w(x,y)\) 是 \(x\) 和 \(y\) 中获胜的手势，特别地，如果 \(x=y\)，那么\(w(x,y)=x=y\)。

我们定义一个对长度为 \(n\) 的字符串 \(s\) 的操作

\[f(s_1s_2\cdots s_n)=w(s_1,s_2)w(s_2,s_3)\cdots w(s_{n-1},s_n) \]

一个长度为 \(n\) 的序列的“最终胜者”是对其施加 \(n-1\) 次 \(f\) 操作得到的字符。

现在，给定一个长度为 \(n\) 的字符串，你需要支持 \(q\) 次操作,操作有两种：

1 k x：将这个字符串的第 \(k\) 个字符修改为 \(x\)。

2 l r：查询这个字符串的第 \(l\) 个字符到第 \(r\) 个字符形成的连续子串的"最终胜者"。

\(n,q\le 2\times 10^5,1\le k\le n,x\in\{R,P,S\},1\le l\le r\le n\)

题解

除非第一个能赢第二个，否则第一个就可以删，同理第二个与第三个，....,一直到第 \(k−1\) 个与第 \(k\) 个。因此我们只需要这么不断操作就能得到最终答案。

维护一个栈，满足第 \(i\) 个元素会输给第 \(i + 1\) 个元素。从左到右插入字符最终的栈底就是答案。

这样我们就可以 \(\mathcal O(n)\) 地解决单次询问了。

注意到在插入 \(s_i\) 时，栈顶是知道的，它显然是 \(s_{i−1}\)，我们设插入第 \(i\) 个字符的栈大小为 \(f_i\),那么稍微讨论一下就可以得到：

\[f_i= \left\{\begin{aligned} &f_{i-1}+1&&s_{i-1}>s_i\\ &f_{i-1}&&s_{i-1}=s_i\\ &\max(f_{i-1}-1,1)&&s_{i-1}<s_i \end{aligned}\right. \]

这里 \(x>y\) 表示 \(x\) 能赢 \(y\)。

可以证明，答案就是最后一个 \(f_i = 1\) 的位置的 \(s\) 值。这里把取最值去掉，得到

\[f_i= \left\{\begin{aligned} &f_{i-1}+1&&s_{i-1}>s_i\\ &f_{i-1}&&s_{i-1}=s_i\\ &f_{i-1}-1&&s_{i-1}<s_i \end{aligned}\right. \]

那么答案就是取得最小的 \(f_i\) 的位置，可以证明所有最小值的位置的 \(s\) 值
都相同，所以可以随便取一个最小值位置。

这样就变成了区间修改，区间最小值，用线段树维护，总复杂度\(\mathcal O(nlogn)\)。

方法

• 分析暴力算法过程

  可以选择先得到一种较优但不是正解的做法，分析他的过程，考虑优化

• 数字化。

  一个结构，或者一个字符不好进行操作，可以选择用一个数字去代表，这样就可以用一些维护数字的手段进行处理。