NOIP2025模拟赛8总结
liujuhan
·
·
个人记录
NOIP2025模拟赛8总结
前言
睡过头了，开始 10 分钟后才到，不太清醒。
T1
计数问题。
考虑 DP 。
我们用 f_n 表示大小为 n 的排列的所有贡献之和。
那么， f_n = n! *n + \Sigma_{i = 0}^{n - 1} (f_i * \frac{(n - 1)!}{i!} + f_{n - 1 - i} * \frac{(n - 1)!}{(n - i + 1)!}) 。
发现后面的 f_i * \frac{(n - 1)!}{i!} 和 f_{n - 1 - i} * \frac{(n - 1)!}{(n - i + 1)!}) 具有对称性，可以合并。
然后前缀和优化一下就好。
由于不太清醒，所以其实用了很长时间，大约 1.5h 。
T2
由于 T1 用了很长时间，所以看到 Hthntd 打了很长时间 T2 ，所以简单看下题，没什么思路就跳了。
T3
看了一下特殊性质，发现当 t_i=-1 时，就是模板同余最短路。
而且数据：保证最多只有 10个 t_i≠−1 ，保证至少有一个 t_i=−1 。
正解绝对与同余最短路有关。
于是先打同余最短路，之后考虑正解。
直接在同余最短路上加一个状压 DP 好像就好了。
打完，开始调大样例，结果就第一个过不去。
第一个是： n\geq 10 且对于 i≥2，1≤t_i≤3 。
但是数字有点大，于是调到结束都没跳出来，只好交了。
T4
没看。
赛后
$T2$ $0$ 分。
正解是当 $ t =1$ 时，暴力。
否则，由于取模后数字均匀分布（重要性质），所以当 $t^p>>n$ 的时候，肯定是有解。
那么p大约为36，直接折半搜索即可。
赛时没人过……
$T3$ $90$ 分，还挺高，数据水了。
正解是先跑同余最短路，然后分组背包，用二进制分组优化即可。
$T4$ $0$ 分。
正解是用组合意义想 $DP$ ，用 $DP$ 算答案，然后平衡树维护矩阵。
前面 $DP$ 挺困难，后面难打还要卡常，所以困难。
感觉学到了。