BJOI 2018 大部分题解

那道人类智慧题咕掉了……

求和太简单了，就 8 写了

链上二次求和

给出一个长度为$n$的整数序列$a$，有$m$次操作，要求支持区间加，询问

$$f(l,r)=\sum_{i=1}^n\sum_{j=i}^n[l\le j-i+1\le r]\sum_{k=i}^j a_k \pmod{10^9+7}$$

$n\le 2\times 10^5,m\le 5\times 10^5$。

线段树

首先有一个小差分。

如果这个序列是一个环，那么答案就很好求。断成链之后，有些区间就不能统计到。对于长度为$x$的区间，那么$a_{n-x+1}$会少统计$1$次，$a_{n-x+1}$少统计$2$次……，$a_n$少统计$x-1$次。同理，$a_1$少统计$x-1$次，$a_2$少统计$x-2$次，以此类推。

那么对于长度小于等于$x$的区间，则系数就是$A=\{1,3,6,10，\cdots\}$，也就是$B=\{1,2,3,\cdots\}$的前缀和。只要能快速维护带系数的区间和即可。那么使用线段树维护，也就转化为，快速求出这两个序列的区间和。其中$1,2,3,\cdots$的很好求，而$1,3,6,\cdots$可以求出前缀和公式$S(i)=\frac{i(i+1)(i+2)}{6}$，当然也可以预处理。

然后还需要把$\sum_{L\le i\le R} A_ia_i$给转化为$\sum_{L\le i\le R}A_{i-L+}a_i$，那么这个可以用$\sum_{L\le i\le R}B_ia_i$和$\sum_{L\le i\le R}a_i$来辅助计算。处理一下细节即可。

时间复杂度$O(n\log_2n)$。

代码

治疗之雨

给你$m+1$个数，第一个数值为$p$，有上界$n$和下界$0$，其他$m$个数值为$\infty$，没有上界也没有下界。

你每次会进行如下操作：

1. 等概率随机选择一个没有达到上界的数并把它$+1$。如果没有就不操作。
2. 进行$k$次：等概率随机选择一个没有达到下界的数并把它$-1$，如果没有就不操作。

问期望进行多少次操作后第一个数会达到下界。如果第一个数无法达到下界输出$-1$。

$1\le p\le n\le 1500,0\le m,k\le 10^9$。

高斯消元 期望 卡常 海森堡矩阵

设$f_p$表示第一个数值为$p$时的期望。在一个回合，它有概率$+1$，也有概率$-j$。设$p_j$表示一回合减$j$的概率，易得

$$p_j=\frac{\binom{k}{j}m^{k-j}}{(m+1)^k}$$

（若$j>k$则$p_j=0$）

另一方面，设$g_j$表示第一个数值为$j$时，一回合就达到下界的概率。容易发现

$$g_j=\sum_{x\ge j}p_x=\sum_{x=j}^k p_x$$

那么现在就可以容易地得到$f$的关系式：

$$f_i=\frac{m}{m+1}\left( g_i+\sum_{j=0}^{i-1}p_j(f_{i-j}+1) \right) + \frac{1}{m+1} \left( g_{i+1}+\sum_{j=0}^ip_j(f_{i+1-j}+1) \right) \quad(i<n)$$

特殊地，$f_n=g_n+\sum_{j=0}^{n-1}p_j(f_{n-j}+1)$。

不妨把$g$去掉，得到

$$f_i=\frac{m}{m+1}\left( 1+\sum_{j=0}^{i-1}p_jf_{i-j} \right) + \frac{1}{m+1} \left( 1+\sum_{j=0}^ip_jf_{i+1-j} \right) \quad(i<n)$$

特殊地，$f_n=1+\sum_{j=0}^{n-1}p_jf_{n-j}$。

这时容易想到高斯消元。而$f$是一个海森堡矩阵，可以使用一些技巧做到$O(n^2)$。

注意要特判$m=0$的情况。

代码

染色

给一个无重边自环的无向图， 每个点分别给了一个大小为$2$的颜色集合，你只能从这个集合中选一种颜色给这个点染色。要求没有两个相邻的点被染了相同的颜色。

求是否无论给定的颜色集合是什么，均有办法按照要求染色。Yes or no。

$1\le n\le 10^5.0\le m\le 2\times 10^5$。

构造 图论 盲猜

如果不是二分图那么显然是 NO。

考虑给你一个环$a\to b\to c\to d \to a$，那么你可以构造$a:\{A,B\},b:\{B,C\},c:\{C,A\},d:\{A,B\}$来钦定$a$必须选颜色$A$。因为如果$a$选$B$的话会和$d$冲突。长度更大的环同理。

既然我们能钦定一个点的颜色，那么只要存在一个环与$a\to b\to c\to d\to a$的环共边数小于等于$1$，就意味着我们可以构造出 NO 的情况了。这里要注意，如果有一条共边，仍然是可以构造出 NO 的。

因此总结一下，判定方式如下：

1. 如果不是二分图，则 NO；
2. 删掉所有的 1 度点（拓扑）后，如果存在某个点不在任何一个简单环上，则 NO；
3. 如果存在某个点度数大于$3$，则 NO；
4. 如果存在两个相邻的$3$度点，则 NO；
5. 如果都没有，那么就是 YES。

由于使用了一些 STL 数据结构，因此我实现的时间复杂度是$O(n\log_2n)$。

代码

二进制

若一个 01 串能在任意重排后变成一个 3 的倍数的数的二进制表示（可含前导 0），称这是好的。比如 101,000,11 都是好串。

现在给你一个长度为$n$的 01 串$s$，要求支持$m$次操作：

• 单点修改
• 询问满足$l\le x\le y\le r$的$s[x,y]$中有多少个好串。

分类讨论

容易发现，满足以下任意一个条件的都是好串：

1. 有偶数个 1。
2. 有奇数个 1，且有至少 3 个 1 和至少 2 个 0。

这个不好算，我们考虑计算不是好串的串的个数，那么不是好串的串就是：

1. 有 1 个 1，有任意个 0；
2. 有奇数个 1，没有 0；
3. 有奇数个 1，1 个 0。

上述三者有一部分算重了，因此要减去

1. 只有 1 个 1，没有 0；
2. 只有 1 个 1，1 个 0。

的个数。

这 5 个都可以简单地使用数据结构维护。

使用 set+ 树状数组实现，时间复杂度$O(n\log_2n)$。

代码