省选模拟赛(III)

冲刺省选3月1日第二十四场

\(t1\) 可以列出 \(nm\) \(dp\)，看到式子中有自变量相乘的形式觉得不能矩乘，注意到模数较小，应该会有循环节，但是并不会证明其长度，于是先做下一题
\(t2\) 完全没有思路，开始打暴力，但是第一次意识到 \(string\) 的好用之处~
\(t3\) 一直以为是点分树之类，只打个暴力

A. 排队

设 \(f[n][m]\) 表示答案，则有转移 \(f[n][m]=(n-2(m-1))f[n-1][m-1]+2mf[n-1][m]\)
可以对于固定的 \(n\) 的把第二维整体考虑，出现循环节即可停止

更为科学的做法是矩阵的循环节是固定的
那么求出 \(mod\) 个不同的转移矩阵再前缀和即可

一个更普遍而巧妙的做法是考虑从大到小加入，设 \(f[i][j]][k]\) 表示目前加入多少个数，形成了 \(j\) 个山峰，形成了 \(k\) 个独立联通块的方案数
可以发现这样的转移是与 \(i\) 没有关系的，那么对于后两位求出矩阵即可

B. 昵称

求出 \(kmp\) 自动机，求出 \(f[i][j]\) 表示答案串为 \(i\) 时匹配到模式串 \(j\) 时的方案数
可以理解成倒序的 \(dp\)，转移时 \(f[i][j]<-f[i-1][to[j][k]]\)，其中 \(to[j][k]\) 表示转移指针
这样初始化为 \(f[0][n]\)，表示最终匹配的了 \(n\)
注意的细节包括要把 \(n\) 位置的所有指针都指向自己，枚举答案时倒序

C. 帝国防卫

大概有两种做法：
求出树的 \(bfs\) 序，对于修改的每一层可以放到线段树上连续区间进行维护
一个效果更好的方式是将询问离线，用类似于整体二分/cdq的方式求出每个点被改成合法的时刻，此时暴力跳父亲打标记就可以了
但是时间复杂度都为 \(nlog^3n\)，据说有复杂度正确的虚树做法？

冲刺省选3月4日第二十五场

C. 过路费

枚举完交费的最小的边后，把更小的边设为零，此时最大的问题在于如何使更大的边选取条数 \(=k\)
直接跑会选多，那么不妨直接先都减去一个 \(cur\)，跑完以后再加上 \(k* cur\) 加回来，这样就变成之多不少了，而最终答案一定也包含在内。

冲刺省选3月5日第二十六场

又是被蠢到的一场……
\(t1\) 发现了第二个条件只要针对约数来求就好了，但是并没有意识到这个条件是充要的，于是建图的时候还一直把这个条件给带上了……
网络流没学最长反链，想了半天也不会搞（以为是np问题），并没有找规律推结论就放弃了
\(t2\) 打出暴力试了试 \(n\le10\) 都跑不出答案，还以为是答案非常大暴力不行，没想到是无解……
\(t3\) 看出了根号重构，但是思维太僵化不会处理操作二

A. 小 G 的约数

有结论是将图按照质因子指数和分层以后最优的是选择一整层
于是直接处理/背包即可

C. 小 G 的 DAG

很容易可以处理出对于操作一的答案，可以顺便记录下来此时的时间
那么对于操作二只需要查询这一段时间内的有效操作即可
可以把重构看成对时间分块，那么其实对于时间的查询就是对于时间维度上的信息的分块查询
整块的信息通过重构时跑一遍拓扑来实现