NOIP2025模拟赛8总结

睡过头了，开始$10$分钟后才到，不太清醒。

计数问题。

考虑 $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$。

由于 $T1$ 用了很长时间，所以看到 $Hthntd$ 打了很长时间 $T2$ ，所以简单看下题，没什么思路就跳了。

看了一下特殊性质，发现当 $t_i=-1$ 时，就是模板同余最短路。

而且数据：**保证最多只有 10个 $t_i≠−1$ ，保证至少有一个 $t_i=−1$ **。

正解绝对与同余最短路有关。

于是先打同余最短路，之后考虑正解。

直接在同余最短路上加一个状压 $DP$ 好像就好了。

打完，开始调大样例，结果就第一个过不去。

第一个是： $n\geq 10$ 且对于 $i≥2，1≤t_i≤3$ 。

但是数字有点大，于是调到结束都没跳出来，只好交了。

没看。

$T1$ $100$ 分。

$T2$ $0$ 分。

正解是当 $t =1$ 时，暴力。

否则，由于取模后数字均匀分布（重要性质），所以当 $t^p>>n$ 的时候，肯定是有解。

那么p大约为36，直接折半搜索即可。

赛时没人过……

$T3$ $90$ 分，还挺高，数据水了。

正解是先跑同余最短路，然后分组背包，用二进制分组优化即可。

$T4$ $0$ 分。

正解是用组合意义想 $DP$ ，用 $DP$ 算答案，然后平衡树维护矩阵。

前面 $DP$ 挺困难，后面难打还要卡常，所以困难。

感觉学到了。