比赛链接

Solved by qxforever.

给一个长度为 $n$ 的排列，每次可以选任意多个下标，shuffle 这些下标的元素，花费为选中下标的数量。问最优策略下把排列还原为元排列的期望花费。 $n \le 10^5$

假题了。对长度为 $x$ 的循环节，通过样例以及手玩算出 std 是把 $x$ 个一起 shuffle 的，然后能推出形式很简单的式子，设花费为 $f$ ，有 $f_n=\sum_{i=1}^n{\frac{f_i}{i}}$ ，很好实现 。

可惜是假的。比如 $x=4$ ，样例给的花费为 $\frac{34}{3}$ ，其实选 $3$ 个 shuffle 的花费是 $\frac{45}{4}$，更优一些。当时还以为自己算错了，反正比赛的时候硬往 $\frac{34}{3}$ 上凑就完事了。

Solved by qxforever.

问随机 $n\times n$ 的 $01$ 矩阵，满秩的概率是多少。 $n\le 2\times 10^7$

设 $n$ 阶 $01$ 矩阵满秩的数量为 $f_n$ ，有递推关系 $f_i=f_{i-1}\times2^{i - 1} \times (2^i-1)$ ，然后除上 $2^{i^2}$ 就是概率。$n$ 的范围很大，$O(n\log n)$ 是不能通过此题的。需要预处理 $2$ 的幂次以及逆元的幂次做到线性。

Solved by qxforever.

签到题

Solved by qxforever.

签到题

Solved by nikkukun.

给一个 $n \times n$ 的网格，用 $k$ 种颜色给每条网格边框涂色，使得：

1. 所有颜色出现次数相同
2. 不存在同色的环
3. 一行或一列边框至少有两种颜色

构造方案，或说明无解。

首先应当满足 $k \mid 2(n+1)n$，且 $n \geq 2$ 和 $k \geq 2$ 时才有解。

一种构造方法是，先依次把所有横边填满，再把纵边填满。若 $k \mid n$，就在奇数行用 $1, 2, \ldots, k, 1, 2, \ldots, k$ 把横边填满，在偶数行用 $2, 3, \ldots, k, 1, 2, 3, \ldots, k, 1$ 把横边填满。对纵边也这么处理，这样相邻行的横边不会有相同颜色。

否则 $k \nmid n$，直接 $1, 2, \ldots, k$ 一行接一行地连续填下去，不需要对相邻行额外去错开一个颜色，也能让相邻行的横边不会有相同颜色。

这样做出来的图，一个方格中最多有两条边相同颜色，且任意两条横向相邻或纵向相邻的边颜色不同，手玩发现这样的性质是搞不出同色的环的，因此满足条件。

Solved by nikkukun & Potassium.

令 $S(x)$ 表示 $x$ 的十进制表示的数位和，求 $S(A) > S(B)$ 且 $0 \leq A \leq B \leq N$ 的 $(A, B)$ 个数，其中 $N \in [0, 10^{100}]$。

数位 DP。令 $n$ 为 $N$ 的长度，$f(p, x, f_1, f_2)$ 表示处理好了 $[p, n]$ 区间的位置，$S(A) - S(B) = x$，且 $f_1 = [A \leq B],\ f_2 = [B \leq N]$ 时的方案数，则 DP 过程和转移就很好写了。总时间复杂度 $O(n \cdot dn \cdot d^2)$，其中 $d$ 表示十进制数位大小。

奇怪的数位 DP。比赛时忘记咋写正常的数位 DP 了，写了一个不正常的数位 DP。

考虑 $A$ 和 $B$ 公共前缀相同时，实际只需要令不同的后缀位置满足 $A < B$（不取等），且数位和 $S(A) > S(B)$ 即可。假设第一个不同的位置上 $B$ 的值为 $c$，则从小到大枚举 $c$，对于当前枚举到的 $c$ 而言，之前所有计算的 $c'$ 都能对 $c$ 做出贡献（都比它小），只要能维护所有 $c' < c$ 且数位和为 $> x$ 的数的个数，即可 $O(x)$ 完成单个 $c$ 的统计与维护。

令 $f(n, x, f_1)$ 表示仅考虑 $[p, n]$ 区间的数 $C$，数位和为 $x$，且 $f_1 = [C \leq N]$ 的数的个数。这个东西是可以和上面无关独立计算的，当考虑 $[p, n]$ 且枚举 $c$ 时，只需要用已经计算出来 $f(p + 1, x - c, f_1)$ 就可以得到满足条件的数的贡献。

总时间复杂度同上。

Upsolved by qxforever.

给一个长度为 $n$ 的排列，有 $m$ 次操作，每次操作 $(k_i,x_i)$ 表示将当前排列玩 $x_i$ 次每 $k$ 个人出局的约瑟夫游戏。输出最终的排列。 $n\times m \le 10^6$ ，$x\le 10^9$

每次约瑟夫问题相当于一个置换，玩 $x$ 次相当于置换的 $x$ 次方。在求出这个置换后可以 $n\log x$ 的算出置换的 $x$ 次方。

求解约瑟夫问题的顺序，需要一种数据结构，可以查询当前数的排名 + $k$ 的排名的数。比赛的时候由于没剩多少时间，偷懒用了 pb_ds 库的红黑树，tree.find_by_order() 可以根据排名查询。线段树上二分的常数应该更小。

Solved by qxforever & nikkukun.

给一个长度为 $n$ 的序列，问这个序列是否为一些长度为 $k$ 的排列组成的序列的子序列。比如 $k=3$ ，则 2,3,1,2,3,3,2 是，而 2,3,2,3,2,3 不是 。 $\sum n\le 2\times 10^6$ ，$k\le 10^9$

考虑 dp，设 $f_i$ 表示前 $i$ 个数是否满足，可以从 $\max(i-k,0)$ 转移过来。如果 $i+k > n$ ，也从 $f_i$ 转移到 $f_n$ ， 转移就是判断 $[l,r]$ 区间的数是否最多出现一次。待判断区间的左右端点均有单调性，因此 dp 的时间复杂度是 $O(n)$ 的。

注意到 $k$ 的范围很大，不可能用数组记录每个数出现的次数。 $2e6$ 范围的 map 不能确定效率是否足够高，比赛中采用了离散化通过了此题。

一开始 H 读错题，写完才发现不对劲。后来写的时候也没想清楚数位 DP 的写法，占了大约一个多小时的思考时间。而且码力很弱，中途卡了好几次，以后开到细节题一定要和队友讨论下咋写。主要是对数位 DP 不熟，需要加强相关练习与 DP 技巧。

K 猜了假结论，而且为了把假结论圆回来还贡献了四发罚时，前期题 WA 了两次的时候就应该考虑换人而不是继续救假代码了。话说我经常喜欢先猜结论，但往往都猜不中，没有把握的时候要和队友确认一下正确性。

前面发挥还比较正常。最后 10min 脑子进水，遇到不确定的还是要和队友确认下，厘清思路。