+++ date = "2021-07-22T01:41:00+08:00" draft = false tags = [] title = "2021 杭电多校 (“中超联赛”) 第一场" authors = ["xry111"] +++

就写了两道题，赛后过了一道，我太菜了……

zoto

题意

给定 $f: \{1, 2, \cdots, n\} \rightarrow \{0, 1, \cdots, 10^5\}$。 每次询问 $(x_0, y_0, x_1, y_1)$，问有多少不同的 $f(i)$ 满足 $x_0 \leq i \leq x_1$ 且 $y_0 \leq f(i) \leq y_1$。

做法

qkoqhh 说可以离线，对询问按 $x_1$ 排序，然后做双指针扫描， 每次加入一个新的 $(i, f(i))$ 的时候就把 $f(i)$ 上次出现的 $(i', f(i))$ 删掉，然后就是查询二维平面中矩形内的点数。qkoqhh 说可以用主席树， 然而我想不出来怎么主席树，没有了 wang9897 的 qkoqhh 自己也想不出来。 最后我写了线段树套平衡树被卡常，于是改成按 $x_0$ 倒序排序， 这样就能把线段树换成树状数组压 $2$ 倍常数，然后又 WA 了， 最后暴力对拍出 bug 改对。

Pass!

题意

有 $n$ 个人，一开始球在第 $1$ 个人手里。 每次一个人都能把球传给除了自己以外的任何人。 已知传 $t$ 次球后球回到第 $1$ 个人的情况数模 $998244353$ 是 $x$， 求 $t$ 的最小值。

做法

首先大概可以看出这题要用 BSGS……

我们用 $f(t)$ 表示传 $t$ 次后球不在第 $1$ 个人的方案数， $g(t)$ 表示传 $t$ 次后球在第 $1$ 个人的方案数，那么

$$\left[ \begin{array}{c} f(t) \\ g(t) \end{array} \right] = \left[ \begin{array}{cc} n - 2 & n - 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{c} f(t - 1) \\ g(t - 1) \end{array} \right]$$

求解一下这个矩阵的特征值，发现 $\lambda_1 = n - 1$，对应的特征向量是 $\mathbf{p} = (n - 1, 1)^T$；$\lambda_2 = -1$，对应的特征向量是 $\mathbf{q} = (1, -1)^T$。

初始状态可以分解： $$(0, 1)^T = n^{-1} \mathbf{p} + (n^{-1} - 1) \mathbf{q}$$

可得 $$x = g(t) = n^{-1} (n - 1)^t - (n^{-1} - 1) (-1)^t$$

对 $t$ 分奇偶讨论即可得到两个限制答案奇偶性的离散对数问题， 把 BSGS 板子随便改一下就能限制答案奇偶性了。

Necklace of Beads

题意

有红绿蓝三种颜色的珠子，问 $n$ 个珠子，其中绿色珠子不超过 $k$ 个， 能拼出的不同手环数。手环相同当且仅当能通过二维旋转操作互相重合。 $1 \leq n, k \leq 10^6$。

解法

首先一看就是 “jl0x62 的手环 IV”，肯定是 Pólya。 查 qkoqhh 的板子知道 $10^6$ 以内的数最多有几百个因子， 所以要求枚举因子开环以后能 $\mathcal{O}(n/d)$ 或者 $\mathcal{O}(k/d)$ 地做才能不超时 ($d$ 是因子)。 我一开始推了个看上去很优美的卷积形式公式给了 qkoqhh， 结果把 qkoqhh 演了 (幸亏这题不是模 $998244353$，不然真的可能冲 FFT 冲死)。 后来考虑先放红蓝珠子在往里插绿珠子， 发现本来不合法的方案插绿珠子后可以变得合法，又把自己演了。 最后才发现先放绿珠子再强制往相邻绿珠子之间强行插若干红蓝珠子就行了， $j$ 个绿珠子的方案数似乎是

$$\binom{n / d - j - 1}{j - 1} 2^j$$

其中二项式系数是将 $n - j$ 个其他颜色珠子分成 $j$ 段的方案数 (每段至少一个珠子，每个绿珠子前面插一段)， 而 $2^j$ 是因为 $j$ 段每一段都可以是 “红蓝红蓝红蓝……” 或者 “蓝红蓝红蓝红……”。 然后好像对 $1 \leq j \leq \lfloor k / d \rfloor$ 求和就行了 (如果 $n / d$ 是偶数，$j = 0$ 还有 $2$ 种情况要加上去)。 结果写完才发现算出来不对，分析一番以后发现例如 $n = 3, j = 1$ 的时候， 只考虑了两种情况 “红蓝绿” 和 “蓝红绿”， 而没有考虑把第一个绿之前的那一段循环移位得到的“蓝绿红”，“绿蓝红” 等等。 然后我又开始枚举移位次数演自己， 最后 Leachim 说循环移位以后相当于变成 $j + 1$ 段，允许第一段中没有珠子 (所以有 $n / d - j - 1 + 1$ 个位置可以放格板，需要放 $j$ 个隔板)， 且最后一段的情况完全由第一段确定，即

$$\binom{n / d - j}{j} 2^j$$

种情况，然后这两个加起来就行了：

$$[2 | (n / d)] 2 + \sum_{j = 1}^{\lfloor k / d \rfloor} \left( \binom{n / d - j - 1}{j - 1} + \binom{n / d - j}{j} \right) 2^j$$

但是当时我们俩互相演了半天 (我现在都复盘不出来)，在一项上多乘了个 $2$，最后赛后才改出来。我太菜了。