清华机试题目大概思路2C2176cjbPidK4FBABgmeBe7B3A-开发者社区

麻将猜猜猜：大模拟军训队列 - 加强版：加强版是斜率优化，但是加强加强版不会魔法学校：莫队+线段树，但是时间复杂度是\(O(n\sqrt{n}\log n)\)，最大的测试点的时间是2.75ms偏差：两个数组做差分，然后KMP匹配判断即可鸽子窝：
设\(f_k(n)\)代表对应答案，根据题目列出式子有

\[f_k(n)=\sum_{i=1}^n\sum_{j=1}^n(ij)^k=\sum_{i=1}^ni^k\sum_{j=1}^nj^k=(\sum_{i=1}^ni^k)^2 \]

，于是我们只需要求出

\[g_k(n)=\sum_{i=1}^ni^k \]

即可
根据提示0和提示1，可以构造一个多项式去拟合，但是不是构造\(k\)阶多项式，根据\(g_k(n)\)的式子，可以构造\(k+1\)阶多项式，\(k\)阶多项式渐进意义上肯定小于\(g_k(n)\)；具体表现就是如果只用\(k\)阶多项式，那么是解不出来的，但是\(k+1\)阶多项式可以解出来
由于\(g_k(n)\)是一个\(k+1\)阶多项式，所以可以利用提示2
对于提示3和提示4，我们可以利用\(g_k(n)\)的定义式快速求出\(g_k(1),g_k(2),...,g_k(k+1)\)
然后对提示2进行变换有

\[\begin{aligned} g_k(n)&\equiv\sum_{i=0}^{k+1}g_k(i+1)\prod_{j=0,j\ne i}^{k+1}\frac{n-j-1}{i-j}\pmod p \\ &=\sum_{i=0}^{k+1}g_k(i+1)\frac{\prod_{j=0}^{k+1}n-j-1}{n-i-1}\prod_{j=0,j\ne i}^{k+1}(i-j)^{-1}\pmod p \\ &=\sum_{i=0}^{k+1}g_k(i+1)(n-i-1)^{-1}\prod_{j=0}^{k+1}n-j-1\prod_{j=0,j\ne i}^{k+1}(i-j)^{-1}\pmod p \end{aligned} \]

显然，上面的式子可以依次循环预处理，用费马定理处理逆元即可
应该需要利用提示5的卡常技巧，时间复杂度毕竟是\(O(k\log k)\)
实际上可以不使用快速幂，而是使用这道题目的思想，可以在\(O(k)\)的复杂度内解决
具体可以见提交的代码连通图的方案数：最后的提示挺关键的
子任务1：暴力即可
子任务2：判断即可
子任务3,4,5：首先找出所有连通块，连通块内部的虚边可选可不选，作为最后的乘数，现在相当于有不超过15个点，问连通图的方法数
由于15比较小，考虑搜索或者状压DP
方案数有种trick，利用容斥原理，连通方法数=总方法数-不连通方法数
不连通方法数的计算比较简单，考虑1号点(这里的点指的是连通块而不是原图的点)在最终的不连通的图中，与哪些点是连通的(不妨设为\(2,3,...,k\))，显然这种计数方法不重不漏，于是这种情况的不连通方法数=\(1,2,...,k\)这些点连通的方法数\(\times 2^p\)，其中\(p\)是满足任意一个端点不为\(1,2,...,k\)的边的个数
于是子问题结构就出来了，设\(f[i]\)表示集合\(i\)中的点构成连通图的方案数，标准的状压DP，枚举\(i\)的包含\(i\)中最低位的点的子集\(j\)，然后利用\(f[j]\)更新\(f[i]\)即可
时间复杂度

\[O(\sum_{i=1}^{15}2^{i-1}\binom{15}{i})=O(3^{15}) \]

但是我感觉状压DP的话，可能需要卡常，因为我没有找到很好的预处理方法
所以可以使用搜索，每次都只考虑1号点所在的连通块即可，不需要考虑不包含1号点的集合
这种搜索的方法可以去看看是不是可以通过子任务6Phi 的游戏：先考虑求出每个点是先手必胜还是后手必胜。
设\(n=2^km\)，其中\(m\)是奇数，根据欧拉函数的性质，有\(\phi(2n)=\phi(2^{k+1}m)=\phi(2^{k+1})\phi(m)=(2^{k+1}-2^k)\phi(m)=2^k\phi(m)<2^km=n\)
所以可以知道每猜一次，数字都会变小，所以最后第一次猜到1的人赢
于是就可以利用递推推导出每个点的必胜性，一个点先手必胜当且仅当三种决策得到的点都是先手必输
但是尝试了各种数学技巧，没有发现什么\(O(1)\)的方法在确定\(r\)的时候找出\(l\)的，考虑\(l\)的贡献也算不出来，同时看必胜点和必输点的分布也挺均匀的。最后想到一种歪招，就是\(l\)每少一，发生的变化就是多一个必胜点或者必输点，对概率的影响很小，所以要不到多少个点就收敛了。但是正确性就不好说了，而且不好卡常，总之来说做不来众数：感觉为每个队列开一个队列(元素是元组，记录数值与个数，数值可重复)来记录队列的状况和一个集合(元素是元组，记录数值与个数，按照个数排序，数值不可重复)来记录众数遍历平滑性：设\(f(i)\)表示以\(i\)为根节点的树的答案，\(g(i,j)\)表示以\(i\)为根节点，并且前序遍历的最后一个节点的下一个节点是\(j\)的答案，于是进行分类讨论(下面假设\(l_i,r_i\)分别表示原树中\(i\)的左子结点和右子节点，可能进行调换)
对于\(f(i)\)，假设\(l_i\)在左，\(r_i\)在右，那么有\(f(i)=f(r_i)+g(l_i,r_i)+|a_i-a_{l_i}|\)；对于\(l_i\)在右，\(r_i\)在左同理
对于\(g(i,j)\)，假设\(l_i\)在左，\(r_i\)在右，那么有\(g(i,j)=g(r_i,j)+g(l_i,r_i)+|a_i-a_{l_i}|\)；对于\(l_i\)在右，\(r_i\)在左同理
主要是时间复杂度的估算，如果就这么朴素的计算的话，时间复杂度是\(O(4^{\log_2n})=O(n^2)\)，显然超时
采用经典技巧，记忆化搜索，可以发现，\(f(i)\)的搜索状态空间大小为\(O(n)\)；同时可以利用结构归纳法证明\(g(i,j)\)中，\(i,j\)要么是兄弟，要么\(j\)是\(i\)的某个祖先的兄弟，于是就可以证明其搜索状态空间大小为

\[O(\sum_{i=1}^{\log_2n}i\times2^i)=O(2^{\log_2n+1}\times(\log_2n-1))=O(n\log_2n) \]

于是可以知道时间复杂度为\(O(n\log_2n)\)花店：两个考虑对象，顾客和花，经过尝试，可以考虑花
设\(f[i][0/1]\)分别表示第\(i\)天的话是否补全到\(V\)，则

\[\begin{aligned} f[i][1]&=\max_{1\leq j\leq i-k+1\text{且}b_{j-1}<V}f[j-1][0]+\sum_{l=j}^{i-k+1}c_l-\text{cost}[j][i] \\ f[i][0]&= \begin{cases} \max(f[i-1][1],f[i-1][0]), & \text{if } b_i<V \\ -\infty, & \text{otherwise } \end{cases} \end{aligned} \]

可知时间复杂度为\(O(n^2)\)