Contest Info

date: 2018.08.19 12:00-17:00

practice link

Solutions

A. Rikka with Lowbit

题目大意：定义操作 \(f(x)\) 等概率地成为 \(x+\text{lowbit}(x)\) 或者 \(x-\text{lowbit}(x)\)。给出长度为 \(n\le10^5\) 的数列 \(\{a_i\}\)，\(m\le10^5\) 操作，或者将一个区间的数都从 \(a_i\) 变成 \(f(a_i)\) ，或者询问一个区间的和的期望值是多少，输出期望乘上 \(2^{nm}\) 后对 \(998244353\) 取模的值。

题解：逗你玩题，\(E(f(x))=x\)，处理前缀和即可，\(\mathcal{O}(n+m)\)。

B. Rikka with Burrow-Wheeler Transform

题目大意：

定义字符串\(s\)的一种变换\(BWT(s)\)为将\(s\)的\(n\)个循环串字典序升序排序，字典序第\(i\)小的循环串的末尾作为\(BWT(s)\)的第\(i\)个位置。

给出一个随机的\(01\)字符串\(s\)，随机询问\(m\)次，每次给出两个区间\([a,b]\)和\([c,d]\)，问\(BWT(s[a\cdots b])\)和\(BWT(s[c\cdots d])\)的字典序大小关系。

（\(1\le |S|,m\le10^5\)）。

题解：

因为数据随机，\(s\)的任意两个后缀的lcp不会很长，这题的数据中不会超过\(40\)，那么如果我们将两个后缀的前\(40\)位用long long预处理出来，就可以\(O(1)\)进行比较.

并且因为数据随机，所有\(BWT(s[a\cdots b])\)和\(BWT(s[c\cdots d])\)的lcp之和不会很长，我们可以考虑暴力比较。

这样就需要依次得到\(BWT(s[a\cdots b])\)的每一位，对于开始位置在\([l,r-40]\)的循环串，它们的字典序关系就等价与后缀的字典序关系，对于开始位置在\([r-39,r]\)的循环串，可以利用位运算\(O(1)\)重新计算正确的hash值，排序之后与前一部分进行归并。

前一部分可以用线段树套std::vector记录归并的过程，然后询问时将对应区间的\(\log{n}\)个节点取出，同后一部分进行归并，即可单次复杂度\(O(\log{n})\)。

也可以用主席树维护区间\(k\)小，依次求出\(k\)小来归并，复杂度不变。

时间复杂度\(O((n+m)\cdot(M+\log{n})+\sum|lcp|\log{n})\)，其中\(M=40\).

C. Rikka with Rotate

题目大意：设 \(S\) 是平面上的一个非空整点集，定义 \(f(S,k)\) 表示用 \(k\) 种颜色染 \(S\) 中的点本质不同的方案数。两种方案本质相同定义为，存在平面上的一个点 \((x,y)\)（可以是实数）和一个角度 \(\alpha\)，使得第一种方案绕 \((x,y)\) 旋转 \(\alpha\) 度后与第二种方案相同。给出一个点集 \(P\) 和 \(k\)，求 \(\sum_{S\subset P,S\neq\emptyset}f(S,k)\)。坐标范围 \(\pm10^{8}\)。

题解：注意到如果一个点集旋转后与自己重合，那么必然有它是由若干个以旋转中心为中心的正多边形的所有顶点组成的。而我们知道整点正多边形只有正方形（另外还可能退化成以旋转中心为中点的一条线段的两个端点，或者只有旋转中心这一个点）。数正方形的个数可以枚举两个点作为正方形的一条对角线， hash 判断剩下的两个点是否存在。之后就是简单的 Polya 定理了。

我们以正方形为例，设以某点为中心的正方形有 \(n\) 个，那么这部分的答案为 \(\displaystyle \sum_{i=1}^{n}{n\choose i}\frac{k^{4i}+k^{2i}+2k^{i}}{4}=\frac{(k^{4}+1)^{n}+(k^{2}+1)^{n}+(k+1)^{n}}{4}-1\)，当然这里还需要减去将每个正方形看做两条线段的答案。还需要注意旋转中心有一个点的情况，这个点也是可选的。这题有些卡空间，需要手写 hash 。时间复杂度 \(\mathcal{O}(n^{2})\)。

coldwater’s comment:

不存在整点正 \(n(n> 4)\) 边形是一个比较常用的结论。简单证明，如果存在，设边长最小的一个是 \(A_1A_2\cdots A_n\)，那么把 \(A_i\) 绕 \(A_{i+1}\) 逆时针转 \(90^{\circ}\)，得到的新图形是一个边长更小的整点正 \(n\) 边形，矛盾。同样有理数正 \(n\) 边形也不存在，否则乘上坐标分母的 \(\text{lcm}\) 就是整点正 \(n\) 边形。

D. Rikka with Prefix Sum

题目大意：给出一个长度为 \(n\le10^5\) 的数列，\(m\le10^5\) 操作，每次操作或者给一个区间每个位置都加上一个数，或者将整个数列变成它的前缀和，或者询问区间和，取模。保证询问的次数 \(k\le500\)。

题解：将区间加拆成两个后缀加，区间和拆成两个前缀和。每当有一次变前缀和的操作就给数列的 \(\text{rk++}\) ，对于每个后缀加操作记录它的 \(\text{rk}\) 和位置 \(c\) 。当遇到询问操作的时候，扫一遍后缀加操作统计答案。

若某次后缀加操作与数列当前的 \(\text{rk}\) 差为 \(r-1\)，影响位置与前缀和询问位置的差为 \(c-1\)，加上的值为 \(w\)，那么贡献为 \(\displaystyle w\times\binom{r+c-1}{r}\)。时间复杂度 \(\mathcal{O}(n+km)\)。

E. Rikka with Equation

题目大意：设 \(A\) 是一个多重集，定义 \(f(A,m)\) 为同余方程 \(A_{1}x_{1}+\cdots+A_{n}x_{n}\equiv0\pmod{m}\) 在 \([0,m)^{n}\) 上的解数。给你一个多重集 \(S\) 和 \(M\)，求 \(\displaystyle \bigoplus_{m=1}^{M}\sum_{A\subset S,A\neq \emptyset}f(A,m)\)。

题解：首先证明：\(f(A,m)=m^{|A|-1}gcd(A,m)\)。容易发现 \(A_{2}x_{2}+\cdots+A_{n}x_{n}\equiv0\pmod{\gcd(m,A_{1})}\) 是方程有解的必要条件，且对于任意一个这样的 \(x_{2},\cdots,x_{n}\) 的解，我们恰有 \(\gcd(m,A_{1})\) 个 \(x_{1}\) 的解，因此我们可以递归地计算：\(\displaystyle f(A,m)=\gcd(m,A_{1})(\frac{m}{\gcd(m,A_{1})})^{|A|-1}f(A\setminus \{A_{1}\},\gcd(m,A_{1}))\)。使用数学归纳法即可证明上述结论。

那么对于一个 \(m\)，我们所求即为 \(\displaystyle \sum_{A\subset S,A\neq \emptyset}m^{|A|-1}\gcd(A,m)\)。设 \(f(u)\) 表示 \(u\mid \gcd(A,m)\) 的所有 \(A\) 的 \(m^{|A|-1}\) 之和，\(g(u)\) 表示 \(u=\gcd(A,m)\) 的所有 \(A\) 的 \(m^{|A|-1}\) 之和，那么答案即为 \(\sum_{u\mid m}ug(u)\)。\(f(u)\) 较为容易计算，设 \(\text{cnt}_{u}\) 表示 \(S\) 中 \(u\) 的倍数的数量，那么有 \(\displaystyle f(u)=\sum_{i=1}^{\text{cnt}_{u}}{\text{cnt}_{u}\choose i}m^{i-1}=\frac{(m+1)^{\text{cnt}_{u}}}{m}\)。根据容斥原理，我们又有 \(g(u)=\sum_{u\mid d,d\mid m}f(d)\mu(d/u)\)。这里已经可以计算了，感受了一下复杂度应该是 \(\mathcal{O}(n\log^{2}n\log B)\)。

但是我们还可以继续化简。原式等于： \[ \begin{aligned} &\sum_{u\mid m}u\sum_{u\mid d,d\mid m}f(d)\mu(d/u)\\ =&\sum_{d\mid m}f(d)\sum_{u\mid d}u\mu(d/u)\\ =&\sum_{d\mid m}f(d)\varphi(d) \end{aligned} \] 时间复杂度 \(\mathcal{O}(n\log n\log B)\)。这尼玛还不是 sb 题?

F. Rikka with Line Graph

题目大意：定义边带权的无向简单图 \(G=<V,E>\) 的一个变换 \(L(G)\)，满足：\(L(G)\) 有 \(|E|\) 个点，第 \(i\) 个点对应原图的第 \(i\) 条边。点 \(i,j\) 之间有边当且仅当原图中 \(i,j\) 两边有公共顶点，且边权为原图中 \(i,j\) 两边的边权之和。现在给出一个边带权的无向简单完全图 \(G\)，设 \(G'=L(G)\)，显然 \(G'\) 是连通的，定义 \(d(i,j)\) 表示图 \(G'\) 中点 \(i,j\) 的最短路，设 \(G'\) 有 \(K\) 个顶点，求 \(\sum_{i=1}^K\sum_{j=i+1}^Kd(i,j)\)。

题解：显然 \(K=\frac{n(n-1)}{2}\)。设原图中第 \(i\) 条边的端点为 \(u_i,v_i\)，边权为 \(w_i\)。那么 \(d(i,j)=w_i+w_j+2\cdot \min\left(\text{dis}(u_i,u_j),\text{dis}(u_i,v_j),\text{dis}(v_i,u_j),\text{dis}(v_i,v_j)\right)\)。其中 \(\text{dis}\) 表示原图 \(G\) 的最短路。所以：

\[ \sum_{i=1}^K\sum_{j=i+1}^Kd(i,j)=(K-1)\sum_{i=1}^Kw_i+\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=1}^n\sum_{t=k+1}^n\min\left(\text{dis}(i,k),\text{dis}(j,k),\text{dis}(i,t),\text{dis}(j,t)\right) \]

对于右边这个式子，我们枚举 \(i,j\)，然后把 \(k\) 按照 \(v[k]=\min\left(\text{dis}(i,k),\text{dis}(j,k)\right)\) 排序，然后依次枚举 \(k\)，那么 \(v[k]\) 的贡献就是 \(v[k]\cdot (n-k)\)。这样的复杂度是 \(\mathcal{O}(n^3\log n)\) 的。

我们可以先对 \(\forall i\) 把 \(k\) 按 \(\text{dis}(i,k)\) 排序的结果存下来，那么按 \(v[k]\) 排序的时候，只需要做一个 \(\mathcal{O}(n)\) 的归并即可。复杂度 \(\mathcal{O}(n^2\log n+ n^3)\)。

G. Rikka with Shortest Path

题目大意：

有一个\(n\le400\)个点的简单无向完全图，每条边有\(p\)的概率存在，\(1-p\)的概率不存在，求随机选择一个点\(x\)到\(n\)的最短路（若不可到达则为\(10^9\)）的期望值，取模。

题解：

因为期望的线性性，我们可以先随机选择点\(x\)，再求\(x\)在随机图上到\(n\)的最短路期望。

显然\(x=n\)时期望是\(0\)，否则\(x=1,\cdots,n-1\)的期望值应该相等，最后乘上\(n-1\)即可。

令\(f[i][j]\)表示从\(x\)出发bfs过程中，没有搜到\(n\)且当前最后一层（深度相同）有\(i\)个节点，未访问过的节点有\(j\)个的概率，\(i\)与\(j\)都不包含\(n\)。

令\(g[i][j]\)表示到达\(f[i][j]\)状态之后，最终无法到达\(n\)的概率。

那么可到达的期望就是\(\sum f[i][j]\cdot(1-g[i][j])\)，不可到达的期望就是\(10^9\cdot g[1][n-2]\).

时间复杂度\(O(n^3)\)，空间复杂度\(O(n^2)\).

H. Rikka with Ants

题目大意：在坐标平面上有两只蚂蚁，它们从 \((1,0)\) 开始走，每一步它们会从 \((x,y)\) 走到 \((x+1,y)\) 或 \((x,y+1)\)。第一只蚂蚁不能穿过 \(y=\frac{a}{b}x\)，第二只蚂蚁不能穿过 \(y=\frac{c}{d}x\)，每只蚂蚁会尽可能先往上走，再往右走。求两只蚂蚁经过的公共整点的数量。

题解：显然 \(\frac{a}{b}=\frac{c}{d}\) 时，公共整点有无穷个。

否则，直线 \(y=x\) 上两只蚂蚁走过的区间分别为 \(\displaystyle \left[\lfloor\frac{ax-a}{b}\rfloor,\lfloor\frac{ax}{b}\rfloor\right]\) 和 \(\displaystyle \left[\lfloor\frac{cx-c}{d}\rfloor,\lfloor\frac{cx}{d}\rfloor\right]\)，那么答案即为 \(\displaystyle \sum_{x=1}^{+\infty}\max\left(\min\left(\lfloor\frac{ax}{b}\rfloor,\lfloor\frac{cx}{d}\rfloor\right)-\max\left(\lfloor\frac{ax-a}{b}\rfloor,\lfloor\frac{cx-c}{d}\rfloor\right)+1,0\right)\)。

不妨设 \(\frac{a}{b}>\frac{c}{d}\)，有答案为 \(\displaystyle \sum_{x=1}^{+\infty}\max\left(\lfloor\frac{cx}{d}\rfloor-\lfloor\frac{ax-a}{b}\rfloor+1,0\right)\)。为了后面求类欧方便，把式子变换成 \(\displaystyle \sum_{x=0}^{+\infty}\max\left(\lfloor\frac{cx+c}{d}\rfloor-\lfloor\frac{ax}{b}\rfloor+1,0\right)\)。注意到，当 \(\displaystyle \frac{cx+c}{d}<\frac{ax}{b}-1\) 时，有 \(\displaystyle \lfloor\frac{cx+c}{d}\rfloor-\lfloor\frac{ax}{b}\rfloor+1\le0\)，因此不用计算贡献；而 \(\displaystyle \frac{cx+c}{d}\ge\frac{ax}{b}-1\) 时，有 \(\displaystyle \lfloor\frac{cx+c}{d}\rfloor-\lfloor\frac{ax}{b}\rfloor+1\ge0\)，可以计算贡献。设 \(\displaystyle X=\lfloor\frac{bc+bd}{ad-bc}\rfloor\)，那么答案即为 \(\displaystyle \sum_{x=0}^{X}\lfloor\frac{cx+c}{d}\rfloor-\lfloor\frac{ax}{b}\rfloor+1\)，使用类欧计算即可。

时间复杂度 \(\mathcal{O}\left(\log\max(a,b,c,d)\right)\)。

comment:

取整函数单调不降。

I. Rikka with Zombies

题目大意：

有一个\(n\le2000\)个节点的树，第\(i\)条边上有一个\([l_i,r_i]\)范围内等概率随机的整数高度的栅栏。

共有\(m\le2000\)个僵尸，第\(i\)个僵尸初始位于节点\(a_i\)，并可以跨越高度低于\(h_i\)的栅栏。

问至少存在一个安全的节点（没有僵尸可以到达）的概率是多少， 取模。

题解：

考虑计算不存在安全节点的方案数。

将僵尸按\(h_i\)排序，令\(f[i][j]\)为只考虑\(i\)所在子树，不存在安全节点，且可以到达\(i\)的最强僵尸为\(j\)的方案数。

在dp过程中，若\(j\)当前不在\(i\)子树中，则方案数其实为假设\(j\)可以从外部到达\(i\)的前提下的方案数，但dp做完后根节点的方案数恰好是不存在安全节点且可以到达根的最强僵尸为\(j\)的方案数。

当枚举到子树\(u\)时，首先在\(u\)处的最强僵尸一定可以到达\(u\)，小于它的方案均不合法。

然后，枚举\(u\)的一个儿子\(v\)来更新方案数，对于\(dp[u][a]\)与\(dp[v][b]\)：

• 若\(a=b\)，则\((u,v)\)边一定要能让僵尸\(a\)可以通过；
• 若\(a\not=b\)，则\((u,v)\)边一定不能让\(a\)和\(b\)通过，且\(a\)不在\(v\)子树中，\(b\)在\(v\)子树中。

对于\(a>b\)的情况，维护\(dp[v][b]\)（\(b\) in \(v\)）的前缀和，然后不让\(a\)通过这条边即可；对于\(a<b\)的情况，要不让\(b\)通过，维护\(dp[v][b]\cdot\text{不让$b$通过的区间大小}\)（\(b\) in \(v\)）即可。

时空复杂度\(O(nm)​\).

J. Rikka with Nickname

签到题，序列自动机。

Dirt Replay

F: -4 前三次代码错误但是 TLE，抠常数；算法正确之后，没有把 log 去掉，TLE

J: -1 清空数组没有清 ch[0]