模拟赛

T1

首先不难发现操作2的使用范围一定是一个后缀 ，因为若并非后缀，则中间这段的修改其实并不会对答案产生影响，每次的操作数始终为 $a_n-a_1$

我们发现实际上操作1是不受控的，每次必定只在产生差距的地方造成影响

不妨猜想后缀推平只会进行一次？好像挺显然的，若不是一次则后面再修改一定会花费更高的代价

问题就变成了如何去计算一段前缀跑 k 次的代价

发现每一段区别段的贡献是一个分段函数，所以可以考虑经典的爆仓线段树

然后就做完了？

T2

逆向的矩阵树定理？

假设该图为一个DAG，那么有生成树数量最大为

$$\left(\frac{220}{V}\right)^{V}$$

其是否能够比 $10^{18}$ 更大？ 显然可以

试想一下是否 DAG 的生成树数量一定比一般图更大

哦好像不行，要是 K 中出现了一个非常大的质因子那就没法构造了

但是质因数分解能拿36分（

发现数据范围中 K 单调递增，考虑是否瓶颈在于K

总不能这真的是构造矩阵吧

外向树是入度

我怎么去构造一个矩阵，使得其行列式为 $K$ ？

总不能是差分约束吧

还是不明白当存在一个大质因子的情况该怎么处理

模拟整个矩阵消元的过程，其实就是对于任意 $i<j$ ，做一次

$$a_{j,j} \rightarrow a_{j,j}-\frac{a_{j,i}}{a_{i,i}}a_{i,j}$$
难不成先将 $> \sqrt K$ 的质因子提取出来，考虑在式子中构造？

欸等下，既然每个矩阵都能够被削成一个上三角矩阵

那是不是也就意味着每个图的矩阵都会唯一对应一个DAG的矩阵

也就意味着一个 图能够表示出来的生成树数量的集合 = DAG能够表示出来的生成树数量的集合

既然题面里没说判断无解，那是不是也就意味着一定能构造出这么一棵树？

又不给大样例，遮遮掩掩的

说不定真的是诈骗题

写了

T3

实在是没有不依靠括号数量的算法啊

第一个点也不知道能不能过

可能45？

![[editorial(1).pdf]]

![[随机算法.pdf]]

不妨设上当前为 $i$ ，那么有

$$h(i)=h(i-1)2^{i}+$$