本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-10 22:47:30

记录

ABCD 切了，E 想了想切了，F 没想出来，G 看出是矩阵了没写出来，Ex 没看，但是也很板。总之全很板。

题解

A - 2^N

基本题，略过不表。

B - Batters

模拟基本题，略过不表。

C - Filling 3x3 array

发现确定四个格后就能唯一确定或填法，所以枚举 $a_{1,1},a_{1,2},a_{2,1},a_{2,2}$，之后判断是否能填出合法方案即可，复杂度 $O(30^4)$

D - Union of Interval

用差分前缀和维护每个点是否在最终的并集中，然后对于每个连续段输出即可。

E - Takahashi's Anguish

发现每个人只有一个 $x_i$ 需要在其之后，如果这样连单向边，就是一个基环树森林。如果要尽量满足更多的条件，就只需要在每个环中选一个权值最小的不满足，拓扑排序处理环即可。

F - Cumulative Cumulative Cumulative Sum

推式子，$c_x=\sum_{i=1}^x b_i=\sum_{i=1}^x(x-i+1)a_i$，$d_i=\sum_{i=1}^x c_i=\sum_{i=1}^x\sum_{k=1}^{x-i+1}ka_i$

接着往下拆，$d_i=\sum_{i=1}^x\sum_{k=1}^{x-i+1}ka_i=\sum_{i=1}^x\frac{(x-i+2)(x-i+1)}{2}a_i$

拆开分子得 $(x^2+3x+2)a_i-2xia_i+(i^2-3i)a_i$，用树状数组动态维护前缀 $a_i,ia_i,(i^2-3i)a_i$ 的和，系数直接计算即可。

G - Black and White Stones

考虑朴素 dp，首先要枚举每条边上的白石子数量 $x$，断环为链，设 $f_{i,0/1,0/1}$ 表示考虑前 $i$ 条边，第一条边开头是/否是白色，第 $i$ 条边结尾是/否是白色的方案数，设 $c_i=\binom{d-1}{i}$，转移如下：

• $f_{i,0/1,0}=f_{i-1,0/1,0}\times c_x+f_{i-1,0/1,1}\times c_{x-1}$
• $f_{i,0/1,1}=f_{i-1,0/1,0}\times c_{x-1}+f_{i-1,0/1,1}\times c_{x-2}$

发现是线性转移，用矩阵加速即可，然后发现 $f_1$ 的初始矩阵和转移矩阵相同，直接 $n$ 次方即为答案，答案中有效的为 $f_{n,0,0}+f_{n,1,1}$，对于 $x\in[1,d+1]$ 分别计算，最后加上 $x=0$ 的一种情况即为结果，时间复杂度 $O(2^3d\log n)$

Ex - I like Query Problem

考虑把整除也转化为区间修改，发现若区间最大值和区间最小值整除 $k$ 相等，就可以直接区间修改为相同的值。因此势能线段树，维护区间和以及最值，每次都暴力下到一个可以区间修改的区间进行修改，由于每个区间被除 $\log V$ 次或被修改一次即可以保证整除相等，总复杂度为 $O(n\log n\log V)$