比赛链接

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\times (2^i-1)$ ，然后除上 $2^{i^2}$ 就是概率。$n$ 的范围很大，$O(n\log n)$ 是不能通过此题的。需要预处理 $2$ 的幂次以及逆元的幂次做到线性。

Solved by qxforever.

签到题

Solved by qxforever.

签到题

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 脑子进水，遇到不确定的还是要和队友确认下，厘清思路。