CTime_Pup_314

C (CF1178F Short Colorful Strip)

给定全 \(0\) 序列，第 \(i\) 次操作可以把值相同的区间的值赋值为 \(i\)，给定目标排列，求出操作方案数

有两个很明显的性质，首先，第 \(i\) 次操作区间一定包括值为 \(i\) 的位置，其次，当一个区间被操作后，这个区间与其他区间相互独立

后者是一个很好的性质，意味着对于每个区间只需要关注最小合法位置，枚举区间划分即可，最后区间相乘即可

终于颓废了一天把多项式写的好看了

本文主要是一个模板库，对多项式进行了封装

基础约定

在本文中，多项式的相关运算里面，只说次数不说项数，次数表述较灵活，但如果涉及多项式取模，通常以 \(ti\) 表示一个多项式的次数，\(n\) 表示这个多项式的是在模 \(x^n\) 有意义，其中除多项式加减乘转置以外，其他或多或少都有多项式取模存在，其中包括多项式求导和多项式积分

~K Perm Counting

如果一个排列 \(P\) 满足对于所有的i都有 \(|p_i-i|\ne k\)，则称排列P为合法的，求合法排列数

考虑错排问题就是 \(k\ = 0\) 的特殊情况，这道题用同样做法来做，设 \(f_i\) 为恰好有 \(i\) 个满足 \(|p_i-i|\ne k\) 的方案数，\(g_i\) 为至少有 \(i\) 个满足 \(|p_i-i|\ne k\) 的方案数，则有

\[ g_i\ =\ \sum_{i\le j}f_j \]

Colorful Slimes

有 \(2\) 种操作，花费 \(a_i\) 秒，直接获得颜色 \(i\) 和花费 \(x\) 秒，使得之前获得的颜色 \(i\) 全部变为颜色 \((i + 1)\ mod\ n\)，求收集到 \(0\) 到 \(n-1\) 所有颜色的最短时间

了解题意后，我们发现，每种方案的 \(2\) 操作一定取决于作用二操作次数最多的颜色，所以枚举 \(2\) 操作，滑动窗口最小值查询即可

Anticube

给定 \(n\) 个数 \(s_i\)，要求从中选出最多的数，满足任意两个数之积都不是完全立方数

对于一个数 \(x\) 进行唯一分解，把每个质因子的指数对 \(3\) 取模构造出数 \(a\)，再把 \(a\) 的每个质因子指数相反数对 \(3\) 取模得到 \(b\)，我们发现 \(a\) 和 \(b\) 是一一对应的，贪心取较大的那一个即可，特判 \(x\) 是完全平方数的情况

进行质因数分解时，可以筛到 \(10^{\frac{10}{3}}\) 以内的质数，对于分解后剩下的数，要么是一个质数的完全平方数，要么是质数，判断一下即可

Stamp Rally

一张连通图，\(q\) 次询问从两个点 \(x\) 和 \(y\) 出发，希望经过的不重复点数量等于 \(z\)，经过的边最大编号最小是多少

在 \(Kruskal\) 重构树上倍增二分即可

Mysterious Light

给定光源，求按照题意规则反射的总距离

很容易观察出该题的重复子结构，每次可以看作从一个平行四边形的右下角向外发射，不妨设 \((a,\ b)\) 来表示平行四边形的两边即初始状态有 \((n-x,\ x)\)

我们尝试用 \((a,\ b)\) 推出下一个平行四边形的状态，显然

题面描述

给定区间集合，交集不为空的互相连边，求所有生成树数量

题解

看见生成树就想到了矩阵树定理骗分，结果发现审错题了，就自闭了

智商什么时候可以练上去啊

根据题意，最后树的形态一定是有区间可以向只有相交关系的区间连边，且后者连的区间不能与其相交，向自己子区间连边时，子区间不能相交

题面描述

给定集合 \(A\) 和 \(B\)，求完全匹配满足 \(\sum[a_i>b_i]-[a_i\le b_i]=k\) 的方案数

题解

首先，题意即是要求匹配满足 \(\sum[a_i>b_i]=\frac{n+k}{2}\) 的方案数，假设状态 \(h_{i,j}\) 表示前 \(i\) 个 匹配满足 \(\sum[a_k>b_k]=j\) 的方案数

考虑转移的顺序，发现对于当前决策\(a_k>b_k\)而言，必须考虑当前状态下有多少满足的 \(b_k\)，这就要求我们一开始把两者排序，则当前符合决策的 \(b_k\) 必定有 \(j\) 个已选，即有转移

\[ h_{i,j}\ =\ h_{i-1,j}+h_{i-1,j-1}\times(less_i-(j-1)) \]

题面描述

在图上随机游走，有一个终止节点，每次经过获得该边权的分数，构造边权赋值方案，使获得的边数期望次数最小。

题解

首先，初步转换为算出每条边的期望经过次数，期望经过次数小的边权大

之后，我们发现直接求边的期望不好求，即转化为点的期望，列出等式