2024NOI准备

考虑 $k$ 个确定的人把问题分成若干长度固定的段, 设长 $l$ 的段内有 $j$ 个人的贡献和是 $f_{l, j}$, 则 $[x^{m-k}] \prod_{l\in S} \sum_j f_{l, j}x^j$ 即为答案.

考虑 $f_{l, j}$ 怎么求, 显然相当于 $j+1$ 段, 和为 $l+1$, 求每段长度乘积的和, 这个是经典的, 一段的贡献显然是 $\dfrac{x}{(1-x)^2}$, 于是总贡献是 $\dfrac{x^{j+1}}{(1-x)^{2j+2}}=\binom{l+j+1}{l-j}$ 即可.

然后两端点的段要特殊处理(不含第一段的贡献), 方法一样.

[ARC101F] Robots and Exits

容易发现洞把序列分成若干段, 对于任意一段其一定是左边的点从左边出右边的点从右边出, 所以其实相当于数合法 $01$ 序列, $0$ 表示某个机器人从左边出 $1$ 表示从右边出. 然后考虑段间的限制, 设 $i$ 到左右出口的距离分别为 $l_i, r_i$, 则若 $l_i>l_j, r_i<r_j$, 则有 $a_i=1\to a_j=1, a_j=0\to a_i=0$.

那么所有选 $0$ 的顶层区间(没有祖先选 $0$), 容易发现它们唯一确定了方案, 要求仅为不能有包含关系, 于是按 $l$ 排序就是简单二维数点.

或者看成把 $(l_i, r_i)$ 画到平面上, 那么相当于选了一条左下到右上的分界线.

复杂度单log.

[AGC032F] One Third

考虑相当于每次插入一个红点后就在左右各 $\dfrac{1}{3}$ 处分别放置蓝点和绿点, 最后求最小的异色点对距离.

则按照第一次插入把环分成三份, 容易发现三份是等价的, 则问题变成了给定一条长 $l$ 线段, $n-1$ 次随机一个位置随机一个颜色放一个点, 问最小异色点对距离期望.

考虑怎么去除异色的限制, 考虑枚举前 $k$ 小的段都是同色的, 容易发现概率是 $\dfrac{1}{3^k}$. 那么只要计算长 $l$ 的线段上随机撒 $n-1$ 个点, 第 $k$ 段期望长度.

那么最短的是好求的:

$$
E(X)=\int_0^{\frac{l}{n}} P(X\ge x)dx = \int_0^{\frac{l}{n}} (l-nx)^{n-1}dx=\dfrac{1}{n^2}
$$

这里第二个等号是考虑相当于分成 $n$ 个长至少为 $x$ 的线段, 则先把它们减去 $x$ 就成了在 $1-nx$ 的线段上选 $n-1$ 个点.

考虑次短, 相当于剩下 $n-1$ 段中最小值, 则先都减去最小值, 于是有

$$
E(X_2)=E(X)+\int_0^{\dfrac{1}{n}} P(X=x) \dfrac{l-nx}{n^2}dx=E(X)+\dfrac{1-nE(X)}{(n-1)^2}
$$

得到

$$
E(X_k)=\dfrac{1}{n}\sum_{i=0}^{k-1} \dfrac{1}{n-i}
$$

就做完了.

[AGC044E] Random Pawn

随机游走题, 设从位置 $i$ 开始最大期望价值为 $f_i$($0$ 起始), 有

$$
f_i=\max(a_i, -b_i+\dfrac{1}{2}(f_{i-1\bmod n}+f_{i+1\bmod n}))
$$

显然 $a$ 最大值处 $mx$ 有 $f_{mx}=a_{mx}$, 断环成链.

想起来 $b_i=0$ 的时候这个题是 USACO 2018 P A. Balance Beam, 考虑如何转化. 则设一些系数 $c$ 使得令 $g_i=f_i+c_i$, 有 $g_i=\max(a_i+c_i, -b_i+\dfrac{1}{2}(g_{i-1}+g_{i+1}-c_{i-1}-c_{i+1}))$, 则只要 $c_{i-1}+c_{i+1}=-2b_i$, $c$ 是容易递推的.

[ARC133E] Cyclic Medians

好巧妙

不知道干啥就先拆贡献, 转化成最后 $a\ge x$ 的方案数, 则容易想到 $<x$ 的数为 $0$, $\ge x$ 的数为 $1$, 称 $a$ 改变当且仅当 $x=y$(此时后面的状态与前面无关), 分类讨论:

若存在 $x=y$, 则 $a$ 于 $A$ 无关, 发现已经没有什么阻止它对称了, 也就是 $x$ 的方案数和 $x, y$ 都翻转后 $V-x+1$ 的方案数是一样的, 而 $x, y$ 翻转会让不合法和合法翻转, 于是 $cnt_x+cnt_{V-x+1}$ 就是总方案数减去不存在 $x=y$ 的方案数再除 $2$.

对于不存在 $x=y$, 限制是很严格的: 设 $g=\gcd(n, m)$, 则有序对 $(x_i, y_j)$ 存在当且仅当 $i\equiv j\pmod g$ 的, 把所有模 $g$ 相等的位置拿出来设为 $S$, 则 $\forall i, j\in S, x_i=x_j, y_i=y_j, x_i\ne y_i$. 于是方案数可以直接统计了.

复杂度除快速幂和 $\gcd$ 外线性.

[think] 核心性质: 对称

[ARC133F] Random Transition

[trick] 考虑转化问题, 把 $\dfrac{x}{n}$ 的概率加一否则减一的概率凑出来, 则对于一开始在 $a$, 最后为 $b$ 的概率, 等价于 $n$ 个硬币有 $a$ 个正面向上, $k$ 次随机翻一枚, 最后有 $b$ 个正面向上的概率.

那么每个硬币独立了, 于是设EGF, 用 $x, y$ 表示翻动次数和硬币个数, 有

$$
\begin{gathered}
F_0(x)=\sum_{2\nmid i} \dfrac{(x/n)^i}{i! }y+\sum_{2\mid i} \dfrac{(x/n)^i}{i! }=\dfrac{(1+y)e^{x/n}+(1-y)e^{-x/n}}{2}\
F_1(x)=\sum_{2\nmid i} \dfrac{(x/n)^i}{i! }+\sum_{2\mid i} \dfrac{(x/n)^i}{i! }y=\dfrac{(1+y)e^{x/n}-
(1-y)e^{-x/n}}{2}
\end{gathered}
$$

则答案的EGF是

$$
\begin{gathered}
Ans(x)=m! n^{-m}[x^m]\sum_i w_i F_1^i(x) F_0^{n-i}(x)\
\text{let}\ A(x)=(1+y)e^x, B(x)=(1-y)e^{-x}. \

Ans(x)=m! n^{-m}2^{-2n}[x^m]\sum_i w_i(A+B)^i(A-B)^{n-i}

\end{gathered}
$$

考虑 $A^iB^{n-i}$ 的系数即

$$
\begin{gathered}
[x^i]\sum_i w_i(x+1)^i(x-1)^{n-i}=\
[x^i] (x-1)^n\sum_i w_i (\dfrac{x+1}{x-1})^i
\end{gathered}
$$

于是对 $\sum_i w_ix^i$ 多项式复合得到和式部分, 再卷 $(x-1)^n$ 即是系数多项式设为 $\sum_i c_ix^i$.

则 $[x^m]\sum_i c_iA^iB^{n-i}=[x^m]c_ie^{(2i-n)x} \cdot (1+y)^i(1-y)^{n-i}=c_i\dfrac{(2i-n)^m}{m! }(1+y)^i(1-y)^{n-i}$

和上面的形式一样! 于是 $y$ 的系数直接就取出来了.

[ABC238Ex] Removing People

时间倒流考虑往位置填人, 要求是加人时有一个相邻点指向自己, 此时有一个很局部的性质, 这个点的贡献只和相邻点有关. 于是考虑区间dp, 设 $f_{l, r}$ 表示 $l, r$ 已经加入, 然后填好中间的这个方案数. $g_{l, r}$ 表示权值和.

转移就是考虑第一下填到哪, 然后把两边乘起来分配标号.

P7718 「EZEC-10」Equalization

显然要差分 $c_i=a_i-a_{i-1}$, 考虑如果你的操作有一端连着端点那么相当于单点修改, 否则是给 $c_i\gets c_i+x, c_j\gets c_j-x$ 这样.

那么对第二类的修改连边 $i\to j$, 最优解一定形成若干棵树, 对每棵树如果所有点原来的 $\sum c_i\ne 0$ 还必然要用一次单点修改. 于是去dp子集划分即可, 每个子集对应一棵树.

然后要求方案数, 显然不会有相同的方案, 算一棵树的时候上个Caylay, 对于有自环的多乘个 $2n$($2$ 是因为单点修改可以操作 $[1, x]$ 也可以操作 $[x, n]$), 就做完了.

复杂度 $3^n$

Shake It!

首先转化成最大流.

设 $f_{i, j}$ 表示 $S\to T$ 形的图操作 $i$ 次得到的图有 $j$ 的流量, $g_{i, j}$ 表示 $S\to a\to T$ 形的图操作 $i$ 次有 $j$ 的流量, 则 $g_{i, j}=\sum_{k, a, b, \min(a, b)=j-1} f_{k, a}f_{i-k, b}$. 是显然的, 复杂度是 $n^4$, 而 $g$ 转移到 $f$ 的时候注意此时 $g$ 中相同的方案是不区分的, 则枚举 $i, j$ 的方案用了多少个, 有 $f_{i, j}=f_{i-kj, j-kj}\cdot \binom{g_{i, j}+k-1}{k-1}$. 就做完了吧!

[ABC231G] Balls in Boxes

对一个盒子: $F(x)=\sum_i \dfrac{(a_i+i)x^i}{i! }=(a_i+x)e^x$, 卷起来提取 $k$ 就是答案.

要算

$$
[x^m]e^{nx}\prod_i (a_i+x)
$$

右边次数很低, 诶这不做完了?

[ABC242Ex] Random Painting

小球是在干什么, 装神弄鬼, 随机一个区间的意思

但是好厉害的题

显然可以离散化令 $n$ 变成 $m$ 的同阶.

Sol1

一个做法是min-max反演, 考虑对于一种方案, 所有方块被染色的时间组成多重集 $S$. 则

[trick] $\max(S)=\sum_{T\subset S} (-1)^{T+1} \min(T)$, $E(\max(S))=\sum_{T\subset S}(-1)^{T+1} E(\min(T))$.

于是考虑求一个子集的最小覆盖时间期望, 即第一次存在一个区间和这个集合有交的期望. 若与集合 $T$ 相交的区间有 $k$ 个, 显然期望是 $\dfrac{m}{k}$, 则dp设 $f_{i, j}$ 表示考虑前 $i$ 个格子的子集合 $T$, $i$ 必选, 与 $T$ 相交的区间有 $j$ 个的带容斥系数方案数. 转移是考虑上一个选择的元素 $j$ 从 $j$ 转移过来. 暴力复杂度是 $n^2m$. 可以线段树做到 $n^2\log n$

Sol2

考虑一个状态 $S$ 是当前已经染色的区间的集合, 显然转移形成dag, 有

[trick] 对DAG, $\text{停时期望}=\sum_{S\text{不合法}} \text{S出现的概率}\times \text{离开状态S的期望时间}$.

离开有 $S$ 的期望时间显然是 $\dfrac{m}{\vert S\vert}$, 则要算 $p_i$ 表示选了 $i$ 个区间还没结束的概率.

哦, 做法一等价于算这个的时候用二项式反演钦定若干点必然不被覆盖吧

dp, 把区间按左端点排序, $f_{i, j, k}$ 表示考虑前 $i$ 个区间, 覆盖了 $[1, j]$, 选了 $k$ 个区间, 当前区间必选的概率, 转移只要求上一个区间的右端点能覆盖当前区间左端点.

注意到 $k$ 和给定区间无关, 设 $F_{i, j}(x)=\sum_{k=0}^m f_{i, j, k}x^k$, 则可以用同样的方法对任意常数算 $F_{i, j}(C)$, 于是最后来一个拉插就行了.

[trick] dp时强硬的用多项式表示一维并维护点值

复杂度和上面的做法一样.

P4707 重返现世

随便开一个minmax反演题. 来学minmax容斥证明, 基本思路就是 $C_1(S)=\sum_{T\subset S} f(T)C_2(T)$, 其中 $C_1, C_2$ 可能是第几大/小状物, 然后改为枚举右边 $C_2(T)$ 的值列组合数, 再套一下二项式反演.

这个题要求第 $k$ 小, 但其实第在知道集合总大小的情况下第 $k$ 小和第 $k$ 大是一样的, 发现对于一个集合它的最小值是好球的, 我们来推一推. 我们希望有 $\mathrm{kthmin}(S)=\sum_{T\subset S} f(\vert T\vert)\min(T)$

考虑右边枚举最小值在集合中的 $rank$ 是 $y$(集合最小值rank为 $1$)值是 $v_y$, 则为 $\sum_{y=1}^{\vert S\vert} v_y\sum_{i=1}^{\vert S\vert-y+1} \binom{\vert S\vert-y}{i-1}f(i)$, 于是要求 $\sum_{i=1}^{\vert S\vert-y+1} \binom{\vert S\vert-y}{i-1}f(i)=[y=k]$, 这不是二项式反演吗, 于是 $f(i)=\binom{i-1}{\vert S\vert-k}(-1)^{i-\vert S\vert+k-1}$

于是这个题, $\mathrm{kthmin}(S)=\sum_{T\subset S}\binom{\vert T\vert-1}{\vert S\vert-k}(-1)^{\vert T\vert-\vert S\vert+k-1}\min(T)$.

于是我们想算 $g_i=\sum_{\vert T\vert=i} \dfrac{m}{\sum_{j\in T} a_j}$, 对所有的 $i$.

直接背包显然爆炸了, 也就是我们不能把 $i$ 割裂的做, 需要整体维护, 注意到 $g_i$ 在答案中的贡献系数是 $(-1)^{i}F(i)$, $F$ 是不超过 $11$ 次的多项式或者说组合数, 于是做完了. 复杂度 $nmk$.

P5244 [USACO19FEB] Mowing Mischief P

$S$ 中的点两人都要经过, 所以容易发现相当于选若干个点 $(x_1, y_1)\ldots (x_k, y_k)$, 最大化 $k$ 再最小化 $\sum_i (x_i-x_{i-1})(y_i-y_{i-1})$.

那么直接dp, 设 $f_i$ 表示以 $i$ 点为结尾的序列长度, $g_i$ 表示面积, 那么 $g_i$ 只能从 $x_j\le x_i, y_j\le y_i, f_i=f_j+1$ 的地方转移过来. 那么你按照 $f$ 排序转移.

那么 $g_i=g_j+(x_i-x_j)(y_i-y_j)$, 但问题是变量有两个, 贡献形式形如($x_iy_j+x_jy_i+C_j$).

考虑决策单调性, 按 $x$ 排序, 同一层节点一定是 $y$ 单调递减的, 发现 $j$ 有决策单调性(容易发现交叉劣于包含), 随 $i$ 增加 $j$ 减少, 但是还有区间限制, 不同区间限制的决策点不好处理.

那就都搞成同一区间限制, 线段树分治, 把每个区间都拆到线段树上, 同一节点的限制就相同了. 复杂度俩log.

P3438 [POI2006] ZAB-Frogs

二分答案, 只保留大于 $x$ 的, 判连通性, 复杂度是 $nm\log n$, 只要想办法对每个点求最近的坏点距离. 一行一起做是斜率优化.

CF878D Magic Breeding

还挺巧妙.

对值域为 $01$ 的时候, 容易bitset, 同时注意 $n$ 维只有 $2^k$ 种本质不同的情况, 复杂度是 $\dfrac{2^kq}{w}$

对于原题, 考虑 $n$ 维是独立的, 可以先把每维离散化到 $1\ldots k$, 此时值域只有 $1\ldots k$, 再把每个数 $x$ 拆成 $k-1$ 位 $[x>1], [x>2]\ldots [x>k-1]$, 就做完了!

The Ultimate LIS Problem

显然 $n$ 和 $2n+1$ 是有深意的.

考虑LIS转化成最小链覆盖, 然后构造长度分别为 $2, 2, 2, 2, \ldots 3$ 的解.

那么 $2$ 想到匹配, 于是把 $n+1$ 拿出来, $[1, n]$ 的看成右括号, $[n+2, 2n+1]$ 看成左括号, 左右括号数量相等必然存在一个位置可以转的合法, 先转过去.

然后此时如果 $n+1$ 在至少一个匹配的括号对里面显然直接做完了, 否则我们可以把它转到开头, 它必须要当左括号, 则意味着后面必须有两个左括号可以合并, 即 $[n+2, 2n+1]$ 不为升序, 那么一定可以做到. 同时还可以把 $n+1$ 放在最后判定是否有两个右括号可以合并.

那怎么证必要啊, 考虑你总可以把 $n+1$ 转到头上, 刚才说明任意两个左括号不可合并, 任意两个右括号不可合并, 看起来就真的无解了.

然后看下怎么求 $k$ 了, 维护一个括号序, 需要支持单点修改, 找到前缀和的最小值, 循环移位, 找到任意两个同色位置 $i, j$ 满足 $i<j, a_i>a_j$. 平衡树即可.

[AGC038E] Gachapon

设 $p_i=\dfrac{A_i}{S}$, 枚举最后一个元素并在时间轴上分配标号:

$$
1+L(\sum_i p_i \dfrac{(p_ix)^{B_i-1}}{(B_i-1)! }\prod_{j\ne i} (e^{p_jx}-\sum_{k=0}^{B_j-1}\dfrac{(p_jx)^k}{k! }))’\circ 1
$$

显然可以设 $P_i(x)=e^{p_ix}-\sum_{j=0}^{B_i-1} \dfrac{(p_ix)^j}{j! }$, $Q(x)=p_i\dfrac{(p_ix){B_i-1}}{(B_i-1)! }$, 那么我们想求 $[y^1]\prod (P(x)+Q(x)y)$.

那么 $P, Q$ 都作为二元多项式 $Poly(x, e^x)$, 复杂度好像有点超标.

但是, 如果我们对每个 $y$ 维护 $x$ 的点值多项式, 则卷一次是 $n^2$, 一开始为每个 $P_i, Q_i$ 算点值复杂度是 $n^2$, 最后插值回来复杂度是 $n^3$!

也有min-max反演+dp的做法.

[AGC021F] Trinity

考虑从左到右每次填一列, 那么容易想到设 $f_{i, j}$ 表示填了前 $i$ 列, 还有 $j$ 行没有填东西的方案数.

转移是分类讨论, 如果没有新占一列方案数显然是 $\binom j0+\binom j1+\binom j2$, 否则新占 $k$ 列, 如果贡献均来自新占的数, 方案数是 $\binom{k+j}{k}$, 如果只有一个来自其中是 $2\binom{k+j}{k+1}$(作为最大或最小乘 $2$), 否则都来自原来的数是 $\binom{j+k}{k+2}$.

于是 $f_{i, j}(\binom{j}{0}+\binom{j}{1}+\binom{j}{2})\to f_{i+1, j}, f_{i, j}\binom{j+k+2}{k+2}\to f_{i+1, j+k}$

加速转移, 对于第二个转移相当于egf卷 $\sum_k x^{k+2}$, 于是就ntt了.

然后可以不用ntt, 写成GF是二元($e^x, x$ 两元)$m$ 次的多项式, 可以直接转移做到 $m^3$

CF1205F Beauty of a Permutation

见到这个是不是该考虑析合树, 只考虑每个点儿子的贡献, 析点有 $i$ 个儿子贡献 $i$, 合点贡献 $\dfrac{i(i+1)}{2}-1$(都不计算自身, 应该被父亲算).

然后直接对着这个dp就好了啊.

[ARC124F] Chance Meeting

容易想到两人坐标作差, 则实际上只有三个操作(A向下和B向上相同), 那么相当于从 $(0, 0)$ 开始每次向上/左/右走一步, 要求经过 $(0, n)$, 最后到达 $(0, 2n)$ 的方案数.

考虑从 $(0, 0)$ 用 $k$ 步走到 $(0, n)$ 方案数显然是 $\binom{k}{n, (k-n)/2}$, 但这样可能多次穿过 $(0, n)$, 设这个方案数是 $g_i$. 而用 $k$ 步穿过一次的方案数显然是卡特兰数容易计算, 设卡特兰数 $c_i$, $C(x)=\sum_i c_ix^i$, $f_i$ 表示走 $i$ 步第一次到达 $(0, n)$ 的方案数, $F(x)=\sum_i x^i$, 则显然 $G=F\dfrac{1}{1-C}$, 于是 $F=G(1-C)$. 答案只要求 $F^2$.

[ABC254Ex] Multiply or Divide by 2

把乘 $2$ 看成对 $b$ 做除法, 则可以把值域控制下来, 且很有单调性.

于是考虑两个集合中的最大值, 若它们相等显然应该直接匹配掉, 否则尝试把大的除以 $2$ 或判断无解.

[ABC245Ex] Product Modulo 2

看起来可以对每个质因子单独做. 现在对 $p^a$ 做 $n’=n\bmod p^a$ 的子问题.

若 $n’\ne 0$

若 $n’$ 中 $p$ 的次数为 $x$, 那么可以把 $p$ 的因子分开, 如果一个位置选了 $p^i$, 那么非 $p$ 因子可以在模 $p^{k-i}$ 下选. 选 $p$ 因子的方案数显然是 $\binom{k+x-1}{k-1}$.

对于非 $p$ 因子部分, 相当于在以 $p^{a-x}$ 中与 $p$ 互质的数构成的乘法群里算, 容易发现得到每个元素的概率相等, 那么只要算总方案数除以 $\varphi(p^{a-x})$. 显然若位置 $i$ 选了 $p^i$, 那么它有 $\varphi(p^{a-i})=p^{a-i-1}(p-1)$ 种方案. 这部分的方案数是 $\dfrac{p^{k(a-1)-x}(p-1)^k}{p^{a-x-1}(p-1)}=p^{(k-1)(a-1)}(p-1)^{k-1}$.

若 $n’=0$, 直接把所有不等于 $0$ 的减掉即可.

[ARC126E] Infinite Operations

先把数组排序.

容易发现最后一定都是平均值.

不容易发现最优策略一定是每次操作数组相邻两项, 而答案就是 $\dfrac{1}{2}\sum_{i<j} \vert a_i-a_j\vert$.

有了这个直接动态开点线段树就好了.

[think] 不知道干啥你就排个序, 另外记得玩样例.

[ARC126F] Affine Sort

考虑设 $f(x)$ 表示 $c=x$ 时的对答案, 则 $F(k)=\sum_{i=1}^K f(x)$, 如果 $f(x)\sim ax^2$, 那么发现 $F(k)\sim \dfrac{1}{3}ax^3$. 于是如果能求得 $\dfrac{f(x)}{x^2}$ 的极限就赢了.

那么考虑要求 $ax_i+b$ 单调, 等价于要求 $\dfrac{ax_i+b}{k}$ 单调, $k$ 足够大时, 问题近似是 $[0, 1)$ 间连续的. 相当于对问题 $ax_i+b \bmod 1$ 单调, $a, b\in [0, 1]$ 的问题答案做二元积分.

那么对每个 $a$ 考虑合法的 $b$ 的范围, 则存在 $b$ 的条件是 $ax_i$ 是递增排列的循环位移, 或者说放在一个圆上它们顺时针转. 此时 $b$ 的范围是 $a(a_n-a_1)$.

考虑如何刻画循环位移, 等价于 $\sum_i w(x_i, x_{i+1\bmod n})=1$, $w(a, b)$ 表示顺时针 $a\to b$ 的距离. 这个的意思是这么走只会在圆上转一圈.

则注意到 $w(x_i, x_{i+1})$ 是关于 $a$ 的 $O(\vert x_1-x_2 \vert)$ 段函数, 于是它们的和是不超过 $\sum_i x_i\le 5\times 10^5$ 段函数, 每段的值是一个常数, 分段对 $b$ 积分即可.

[ARC128F] Game against Robot

设 $n$ 是 $\dfrac{N}{2}$

先考虑 $p$ 固定怎么做, 设你选择的第 $i$ 个数会被对面第 $r_i$ 次选, 那么能选它的条件是 $\sum_{j<i} [r_j<r_i]+i-1<r_i$, 感觉很复杂.

注意这时两个人不是对称的, 考虑对面选的第 $i$ 个数它本来应该在第 $r_i$ 次选, 那么这个数满足 $r_i\le 2i$. 而你是倒数第 $i$ 次取的数在后 $2i$ 名.

那么直接把序列反过来, 要求你取的第 $i$ 个数满足 $r_i\in [1, 2i]$, 这时候就可以贪心了啊, 显然每次会选当前能选集合中的最大数. 每次加入前面两位, 再删掉集合最大值.

显然要拆贡献, 计算 $i$ 被计算的次数. 那么对这种比大小的考虑缩减值域, 可以变成算前 $k$ 大被算的总次数, 就可以把前 $k$ 大设为 $1$ 剩余的设为 $0$.

那么从前往后每两位分为一组, 设当前集合中 $1$ 的个数为 $x$, 每次显然是 $x\gets \max(0, x+c_i-1)$, 其中 $c_i$ 表示第 $i$ 组中 $1$ 的个数. 而 $x$ 取 $0$ 时就是选了一个 $0$.

画到平面上, 对应了一个每一步走 $(1, 1), (1, 0), (1, -1)$ 的折线, 对应 $c_i=2, 1, 0$, 而如果这一步跨过 $y=0$($c_i=0$ 且 $x=0$)就掰直成走 $(1, 0)$. 然后我们要数掰直次数不超过 $k$ 的折线.

考虑去掉max, 则原来每个掰直都会作为现在新的前缀min, 最后就要求全局最小值大于等于 $v(v<0)$, 即选了 $n+v$ 个 $1$, 限制类似卡特兰数, 考虑反射容斥.

那么先要会算从 $(0, 0)$ 走到 $(x, y)$ 的方案数, 即 $[z^y] (z+2+z^{-1})^n$(注意 $c_i$ =1的方案数是 $2$).

$$
\begin{gathered}
[z^y] (z+2+z^{-1})^x\
=[z^y]z^{-x}(z^2+2z+1)^x\
=[z^{x+y}] (z+1)^{2x}\
=\binom{2x}{x+y}
\end{gathered}
$$

于是反射容斥, $\sum_i c_i=k$ 所以要走到 $(n, k-n)$, 则若接触 $y=v-1$ 反射后要走到 $(n, 2(v-1)-k+n)$ 就是 $\binom{2n}{n+k-n}-\binom{2n}{2(v-1)-k+2n}=\binom{2n}{k}-\binom{2n}{k-2v+2}$. 那么最小值恰好为 $v$ 的方案数就是 $\binom{2n}{k-2v}-\binom{2n}{k-2v+2}$.

要求答案注意要再乘 $0$ 和 $1$ 内部相对顺序.

[ARC115E] LEQ and NEQ

简单题, 对条件容斥, 然后一段的权值是最小的 $a_i$, 直接dp+单调栈.

诶, 可以直接二维dp再数据结构优化一维.

[ARC112E] Cigar Box

显然对一个数的操作只有最后一次有效.

考虑划分成不动, 到前面, 到后面 $3$ 个集合, 要求不动的集合递增, 然后三个集合的值域递增.

那么几乎做完了, 显然不动的集合在 $a$ 上一定是个区间, 那么确定这个区间后, 设左边有 $A$ 个, 右边有 $B$ 个, 则操作可以依据操作的数分成 $A+B$ 类, 方案数是 ${m\brace A+B}$, 对每个数的最后一次操作显然已经确定方向, 前面的任意, 所以乘 $2^{m-A-B}$, 向左和向右互不影响卷起来, 乘 $\binom{A+B}{A}$

[ARC124E] Pass to Next

考虑设第 $i$ 个人传给下一个人 $x_i$, 要满足 $x_i\le a_i$, 则贡献是 $\prod_i (a_i+x_i-x_{i-1})$

那么考虑如果是个序列, 考虑经典的等于每一个里选一项乘起来算贡献, 那么对于当前第 $i$ 个括号, 若选择 $a_i$ 则不管这一位 $x$ 是多少都是 $a_i$, 若选择 $x_i$ 是一个等差数列求和, 若选择 $x_{i-1}$, 则需要和上一项合并是一个平方求和, 就能转移了.

然后因为是环需要断开, 枚举第一个括号选的哪一项即可.

[ARC138E] Decreasing Subsequence

考虑让所有 $a_i\ne 0$ 的 $i$ 向 $a_i-1$, 形成 $n+1$ 个点的有向图, 则合法情况下每个点只能向前连边, 又因为互不相同一定形成若干条链, 每个链是有序的, 也就是相当于划分了若干个集合.

然后考虑一个长 $k$ 的下降序列, 表现为 $k$ 条边 $r_1\to l_1\ldots r_k\to l_k$, 满足 $l_1\le l_2\le \ldots l_k\le r_k \le \ldots r_2\le r_1$, 则容易发现所有点会被这些边分成值域不交的两部分. 于是直接枚举这两部分的大小 $x, y$, 先选出两部分点是 $\binom{n+1}{i+j}$, 两部分分别划分成 $k$ 条链, 方案数是 ${x\brace k}{y\brace k}$, 剩余的部分划分成若干条链是 $\sum_i {n+1-x-y\brace i}$, 就做完了.

[ARC131F] ARC Stamp

考虑反过来, 每次操作相当于把三个字符变成? , 这三个字符可以是ARC, ? RC, AR? , ? ? C, ? R? , A? ? .

考虑? 段一定是从ARC开始, 向右边扩展连续的RC和C, 向左扩展连续的AR和A, 然后可能有两段通过? R? 合并. 而一个字符串可以唯一的划分成若干段 $(AR/A)^aARC(RC/C)^b$, 每段之间是一个单独的R或者连续的不可操作段X.

考虑设如AR, A等这样的是一段, 进行dp: $f_{i, j, 0/1}$ 表示考虑前 $i$ 个段, 用了 $j$ 次操作, 是否当前段和下一段都要被操作成? .

然后此时要注意, 为了钦定不重, 如果一段始终没动, 不应该对它进行操作, 如一个固定的ARC, 如果前后没有依赖它变成? 才能选的段, 那么若它本来是ARC也操作一次会和压根不动的方案重复. 此外对于两个连着的ARC如果中间没有东西, 因为后面的ARC不依赖前面应该在中间添加一个X

复杂度 $nk$

[ARC139D] Priority Queue 2

拆贡献, 枚举 $v$ 计算最后 $\ge v$ 的数个数.

这里甚至不用dp, 考虑若一开始有 $a$ 个 $1$, 加入了 $b$ 个 $1$, 那么每次操作是留下前 $n-x+1$ 大的数, 那么若 $a\le n-x+1$ 显然最后最多有 $n-x+1$ 个 $1$, 否则每次多一个 $1$, 则最后有 $\min(a+b, n-x+1)$ 个. 如果一开始 $a>n-x+1$, 每次如果不加一个 $1$ 就会少一个 $1$, 即 $\max(a+b-k, n-x+1)$ 个.

P9481 [NOI2023] 贸易

考虑算从每个点出发到其他所有点的距离和. 从父亲的答案转移到儿子, 则只要考虑最优解第一步不是走到父亲的点, 那么一定是起点为 $u$ 的第二类边. 那么现在若已有每个点到父亲的距离, 可以暴力更新第二类边的答案(一条第二类边 $u\to v$ 只影响 $v$ 的所有祖先), 于是复杂度是 $n\log^2 n$

P9482 [NOI2023] 字符串

把正串和反串拼到一起SA, 然后就是数 $j$ 满足 $rank_i<rank’j$, $j\in [i, i+r-1]$, $lcp(s{i\ldots j-1}, s_{2j-i\ldots j})<j-i$.

第三个条件很难做, 但其实我们都知道放在这里只是防止它俩相等, 而相等就是回文串, 于是去掉第三个条件做二维数点, 再单独数回文串,
就做完了.

但是我不会求SA啊.

P9478 [NOI2023] 方格染色

喵的读成每次都要询问了.

那么横向/竖向重叠的可以合并, 考虑显然就要求每条线段和其他线段的交集直接扫描线, 然后斜线可以每次枚举判断.

然后 $n, m$ 很大, 可以只管横竖线的情况离散化一下.

P9479 [NOI2023] 桂花树

注意 $k$ 很小.

称 $1\ldots n$ 为旧点, $n+1\ldots m$ 为新点.

首先 $T’$ 拿出 $1\ldots n$ 形成虚树一定是 $T$. 因为已知所有点lca肯定能构建唯一一棵树. 而你可以把任意形状的若干新点作为一组挂到叶子上或插到原树的一条边上.

看第二个限制, $1\ldots n$ 的点对已经确定了动不了, 有祖先关系的一定成立, 情况只有: 子树内最小值和当前组的一个点, 或者组内点对可能非法. 而子树内最小值的时候选旧点总是更优, 所以不会有组间非法.

考虑 $k=0$, $n=0$ 怎么做, 可以直接dp出 $f_{i}$ 表示 $i$ 个点的答案. $n\ne 0$ 之后, 注意对于一个组如果下面还有点相当于挂了一个 $-inf$, 然后此时因为只有大小关系可以直接卷.

但是考虑组的合并是没有前途的, 考虑第二个条件相当于 $1\ldots i$ 的虚树没有大于 $i+k$ 的点, 那么从小到大加点现在已经有一棵虚树, 虚树上有已经填了的点和一些还没填数的点(显然不超过 $k$ 个), 设当前虚树点数为 $c$, 往上新增一个点时可以选择

填到边上或挂叶子, 有 $2c-1$ 种.
在一条边上加一个空点, 成为空点的叶子有 $c-1$ 种.
填一个空点, 然后有一个要求.

注意每个空点创建时, 子树里最小值最大的两个点一定已经有了, 可以确定其是否能填 $i+1\ldots i+k$, 就做到 $tmk2^k$ 了.

[ARC127E] Priority Queue

考虑如何判断一种状态合法, 那么最终一定互不相同, 那么从后往前做, 每次要么删掉一个集合中的数, 要么加入一个比当前集合中最大的数还大的未被加入过的数, 最终要变成空.

那么加入的时候应该加尽量小的数, 删的时候应该删尽量大的数, 而无解是因为加入数的时候没有数可以加.

那么考虑若最后数列是 $s_1\ldots s_{n-m}$, 则删的第 $i$ 个数就是 $s_{n-m-i+1}$, 设要删这个数的时候已经进行了 $p_i$ 次加数操作, 要满足 $n-s_{n-m-i+1}-(i-1)\ge p_i$(即, 这个数后面的空位数比要加的多).

问题就转化为求有序数列 $a$ 满足 $0\le a_i\le a_{i+1}\le m, a_i\ge p_i$ 的方案数. 可以暴力dp

实际上可以分治做到 $n\log^2 n$, 考虑把 $(i, a_i)$ 画到平面上是一个从左下到右上的线, $(i, p_i)$ 也是一条从左下到右上的线, 要求 $a$ 的线在 $p$ 的下面的方案数. 考虑分治, 把这个阶梯用 $x=mid$, $y=a_{mid}$ 两条线分成三部分: 两个子阶梯和中间一个正方形, 求出左下方子阶梯从右边线每个点出来的方案数, 通过一次卷积可以得到右上方的子阶梯从下面每个点进去的方案数, 就递归下去了.

A. [23省选二轮 day1] 移动箱子

$y_i, n, m\le 10^5, x_i\le 10^{11}$

你的操作肯定是从左往右, 如果大了就把多的移到右边. 设 $i\to i+1$ 的移动了 $b_i$, 显然有 $b_i=\max(b_{i-1}+a_i-k, 0)$, $a_i$ 是这个位置数量.

注意相邻的两堆 $a_i, a_j$, 若 $[i, j]$ 中不存在 $b_k=0$, 则可以 $a_i\gets a_i+a_j, a_j\gets 0$, 答案会变化的值是和 $k$ 无关的 $a_j(i-j)$.

于是从大到小扫 $m$, 用链表维护每个堆和前后合并的时间可以做到 $nm$, 因为要堆每个堆算 $\sum_j \max(0, a_i-jk)=a_it-k\binom{t+1}2$, 其中 $t=\lfloor\dfrac{a_i}{k}\rfloor$.

那么显然每个堆的共线是关于 $k$ 的 $O(\sqrt m)$ 段一次函数, 然后一共有一开始的 $m$ 个和合并后的 $m$ 个一次函数, 答案是这些一次函数的和 $O(m\sqrt m)$ 段就做完了.

B. [23省选二轮 day1] 开黑团体

$n\le 28, m\le 5\times 10^5$

暴力是直接FMT, 对 $x$ 处理 $b_x$ 表示 $\cup_{a_i\subset x} a_i$, $x$ 合法当且仅当 $b_x=x$. 复杂度 $n2^n$.

考虑对每一位分开做, 处理 $c_{i, x}$ 表示 $x$ 在第 $i$ 位是否合法, 显然 $x$ 这位为 $0$ 的都合法, 那么把所有满足 $a_j$ 这一位为 $1$ 的 $c_{i, a_j}$ 位置赋值为 $1$ 对这些这位为 $1$ 的地方做FMT, 为 $0$ 的地方不做.

那么要对每一位做这个, 而且每一位恰好自己那一位不做FMT, 于是上个缺一分治, 复杂度是 $\dfrac{2^nn\log n}{w}$

C. [23省选二轮 day1] 123 vs 321

$n\le 5\times 10^7$

考虑假设已经要选 $a$ 个上升, $b$ 个下降, 对上升一定是选最前面的 $1$ 和最后面的 $3$, 对下降一定是选最前面的 $3$ 和最后面的 $1$, 那么现在有 $a+b$ 个上升/下降区间, 每个区间要匹配一个 $2$.

考虑Hall定理, 那么一定是选择一个 $l, r$, 所有在 $[l, r]$ 中的区间都选才是最紧的, 则分别是上升/下降区间的一个区间

todo

[ABC249G] Xor Cards

考虑把 $x$ 插到线性基 $A$ 同时记录对应 $y$, 那么有些元组插不进去, 此时这些元组可以被 $A$ 中的表示, 相当于可以任意选择, 把对应的 $y$ 插入到第二个线性基 $B$.

那么从高到低考虑 $K$ 的位和线性基当前选择的 $x$ 异或值 $X$, 分类讨论, 若 $X$ 和 $K$ 这一位都是 $0$ 则对应线性基元素不能选, $X$ 是 $1$, $K$ 是 $0$ 必须不选, 否则可以选择选/不选, 若选择其中一个就继续, 另一个就可以后面的位和 $B$ 中任意选, 就做完了.

复杂度 $n\log W+\log^2 W$.

CF936E Iqea

注意剩余部分也连通说明给定的点不会成一个环, 考虑如果是个树问题就是点分树简单题了, 问题是可能有很大的块在图上.

考虑一行一个极长连续段作为一个点, 做完了.

[ARC140F] ABS Permutation (Count ver. )

考虑 $M=1$ 的时候, 满足条件的位置形成若干条链, 若确定了链的大小分别为 $a_1\ldots a_k$, 则方案数是 $k! 2^{\sum_i [a_i]>1}$, 即一段贡献 $F(x)=x+\sum_{i=2} 2x^i$. 若钦定有 $i$ 个位置满足限制, 链的数量应为 $n-i$.

但这时候直接做 $n-i$ 次方提取 $k$ 项系数是不对的, 因为可能有两条链实际上是一条, 我们设长 $k$ 的链贡献 $c_k$, $C(x)=\sum_i c_ix^i$, 有 $\dfrac{1}{1-C(x)}=F(x)$, 就可以得到真实的系数了. 然后 $k$ 对的答案是 $(n-k)! [x^n]C^{n-k}(x)$ 对所有 $k$ 求, 实际上是对所有 $i$ 求 $[x^n]C^i(x)$, 转置原理就是对所有 $i$ 求 $[x^i]C^n(x)$ 了.

好吧这地方没必要转置原理吧, $F(x)=\dfrac{2x}{1-x}-x$, $C(x)=\dfrac{x(1+x)}{1-x}$, 则 $[x^n]C^i(x)=\dfrac{x^i(1+x)^i}{(1-x)^i}=\sum_j \binom{i}{j}\binom{n-j+i-1}{n-j}$, 对所有 $i$ 求这个, 拆开卷积就好了.

然后对 $M\ne 1$, 可以考虑 $P^{-1}$, 此时相当于要求不存在 $P_i$ 与 $P_{i+M}$ 的值相邻, 相当于把 $P$ 划分成若干个独立的子问题, 注意子问题的大小只有两种所以分别求答案再卷一下即可.

[ARC118E] Avoid Permutations

注意对 $P$ 累加 $F(P)$ 等于对一条路径累加不能把障碍放到路径上, 放障碍的方案.

但是放障碍的时候要当一个排列放, 发现我们会算乱放的(还剩 $k$ 个没放就是 $k!$), 那么容斥, 算钦定了 $k$ 个在路径上的方案数, 放这些的时候要保证没有同行同列则只要设 $f_{i, j, k, 0/1, 0/1}$ 表示路径走到 $(i, j)$, 放了 $k$ 个, 是否在同行放过, 是否在同列放过的方案数. 复杂度 $n^3$

[AGC053C] Random Card Game

设两堆是 $L, R$, 容易发现最大值不会被删, 所以最后留空的一堆事确定的, 不放设是堆 $L$.

那么只要最小化 $R$ 中元素被删的个数, 容易发现策略是若存在 $L$ 中的元素比 $R$ 中对应元素大就删掉满足这个条件的 $k$ 最大的. 否则删 $L$ 的第一个元素(显然 $L$ 中第一个元素肯定迟早要删). 分析操作次数, 设开始时 $L$ 中第 $i$ 个元素对应 $R$ 中 $k$ 最小的大于它的元素是 $p_i$, 发现答案是 $n+\max p_i-i$.

考虑再拆贡献, 计算 $\max p_i-i\le k$ 的方案数, 然后这个就要求对任意 $i\in [1, n]$, 存在一个 $j\in [1, i+k]$ 使得 $b_j>a_i$.

然后这个直接组合数学乘起来.

[LGR-189-Div. 2]核桃编程 6 月月赛 I & JRKSJ Round 8

T457265 [JRKSJ R8] 网球

设两个合法齿轮分别有 $x, y$ 个, 要求 $ay=bx$, $g=\gcd(a, b)$, 则一组解是 $x=b/g$, $y=a/g$.

显然你唯一能做的就是一起乘一个数.

T375744 [JRKSJ R8] 三七二十一

首先不能有 $\texttt{1, 2, 4, 8}$, 发现满足这个的二的次幂只有 $65536$, 然后随便做了.

T387475 [JRKSJ R8] +1-1

那么 $x$ 自己必须是(, 若 $x$ 旁边有一个(显然可以反复横跳得到大量的(, 如果没有只能是 $x$ 旁边都是), 再一层必须有(, 再往外又是)这样才阻止我们刷括号. 相当于走正反括号交替的路径, 只保留连正反括号的边可以得到一张二分图, 如果 $x, y$ 在同一个连通块上显然直接就判完了, 否则要求 $x$ 去找一个两端都是(的边, $y$ 同理, 最后有个路径长度奇偶性限制.

P10573 [JRKSJ R8] C0mp0nents

注意到 $k\ne 1$ 的时候模 $k$ 的同余类都是子问题, 所以规约到 $k=1$.

此时要想变到 $s$, 因为一个值只出现一次, 变成 $s$ 的点的值一开始一定是一个连通块, 且每个位置数变化都是单调的, 则若最终 $l, r$ 变成 $s$, 和 $[l, r]$ 以外的点无关.

考虑 $s=1$ 的情况, 发现充要条件是每个 $[1, r)$ 的点都能连向比自己大的点, 此时最大值才能不断下降(任意时刻, 最大值所在连通块的初始权值是一个 $[x, r]$ 的区间), 于是对于 $[l, r]$ 就分两部分限制即可. 只要每个点 $u$ 找到与自己连通的小于自己的最大值/大于自己的最小值, 设为 $l_u, r_u$, 那么对 $[l, r]$ 限制是 $\forall i\in [s, r], r_u\lt r$, 另一边也一样.

然后可以扫描 $s$ 的过程中统计答案了.

P10574 [JRKSJ R8] 暴风雪

考虑一次修改 $x$ 对 $f$ 造成的影响, 表现为对到根的路径上的值 $u_i$ 和序列 $val_i$ 对应取max, $val_i$ 自然为 $u_i$ 在这一层的和. 那么注意到若存在 $val_i\ne val_{i-1}$, 必须是因为 $u_i$ 有这个链以外的另一棵子树深度不小于 $dep_x$, 那么容易发现最多有 $\sqrt n$ 个这样的段, 且因为 $val$ 单调递增可以看成 $\sqrt n$ 个根链取max, 树剖容易做到 $n\sqrt n\log n$

需要优化到$n\sqrt n$.

注意到 $u_i$ 满足的性质: 若第 $i$ 段长 $a_i$, 则 $a_i$ 的侧链必须至少长 $\sum_{j=1}^{i-1} a_j$, 所以 $\sum_i \sum_{j<i} a_j\le n$, 可得 $\sum_i \log(a_i)=O(\sqrt n)$, 所以实际上拆到线段树上只有 $\sqrt n$ 个节点.

要能做到 $O(1)$ 定位包含一个区间的最小区间,这个东西考虑猫树,即线段树长度搞成$2^k$,那么只要用位运算求叶子的lca,定位全部区间依次修改并统一pushup就可以做到 $\sqrt n$.

然后要能不带log找所有分段点,那么根号分治,近$\sqrt n$个暴力,而对于后面的点只有存在一个轻子树内点深度大于$\sqrt n$的有可能,这样的点最多有$\sqrt n$个.

然后要能求点$u$子树内深度为$d$的点的和,考虑维护每个点轻子树每一层的和(总量为$n\log n$),在同一条重链上跳就可以直接加,然后用bit维护每层的和,在跳过轻边时查一下.

就$n\sqrt n$了!

ZR Day2 A. 蝴蝶兰

$n\le 2. 5\times 10^6$

注意到只有前缀max造成贡献. 于是把 $h$ 从小到大排序选出前缀max的位置, $f_i$ 表示考虑 $i$ 后面的数, $i$ 为前缀max, 后面的数能承受多大风力, 显然 $h_j<h_i$ 的 $j$ 不会造成影响, 转移就是 $f_i=\max_j \min(f_j, {\dfrac{s_j}{h_j-h_i}})$.

每个数的转移是 $\dfrac{a}{b-x}$ 的形式, 注意到任意两个这样的函数最多有一个交点, 于是有决策单调性, 开个栈可以线性.

[think] 剔除不贡献的元素获得单调性

ZR Day2 B. 风铃草

$n\le 3\times 10^5$

有点难绷, 读成在前面加(了. 那你策略肯定是先把总数弄对了, 然后设 $i$ 处前缀和为 $s_i$, 操作次数就是 $\sum_i \lceil \min(0, s_i-k)/2\rceil$, 其中 $k$ 是在前面添加的)数量.

考虑怎么快速算答案, 一个位置的贡献其实是 $[s_i>k] \lceil(s_i-k)/2\rceil$, 后面的部分每个数在 $k$ 奇偶性确定的情况下是一个一次函数, 于是分块, 对于 $[s_i>k]$ 一个块只有 $\sqrt n$ 种不同的情况, 每个情况维护奇/偶分别对应的贡献即可. 而且注意由于 $s_i-s_{i-1}\in [-1, 1]$, 值域也是 $\sqrt n$ 不用开有序表二分而可以直接开桶维护.

复杂度 $n\sqrt n$

ZR Day2 C. 香雪兰

$n\le 250$

令 $f_{n, i}$ 表示连出长度为 $n$ 的链, 最后一次连链上的边后连了 $i$ 条非链边. $g_{n, i}$ 表示 $f_{n, i}$ 的前缀和. 转移是枚举 $k, L, R$ 表示最后 $f_{n, i}$ 子问题中最后连的链边是 $k\to k+1$, 在这之后左边部分连了 $L$ 条, 右边连了 $R$ 条, 则由 $g_{k, L}$ 和 $g_{n-k, R}$ 转移.

化一下卷积形式维护点值就做完了. 复杂度 $n^4$.

[YDRS#008] 人团圆, 梦也团圆 · 云斗六月 Silver Round

C. 熙攘市场今何在

考虑先让第一个排列变成 $1\ldots n$. 第二个排列形成若干置换环, 限制只发生在每个环内部.

考虑再把一个点拆成两个表示选正面/反面, 则一个置换环拆完了还是环, 限制是相邻两个点不能同时选.

对环算最大独立集是简单的, 就做完了.

D. Yet Another Passing-Ball Problem

对不超过一半考虑容斥掉, 容斥系数显然是不满足一半限制的时刻 $i$ 的个数.

那么可以列出dp $f_{i, j}$ 表示考虑前 $i$ 个时刻, 有 $j$ 个人拿球的带容斥系数方案数, 则

$$
f_{i, j}{k-j \brace l}\binom{n}{l}\to f_{j, l}
$$

然后如果 $l>\dfrac{k}{2}$ 要额外乘 $-1$.

发现第二维很小, 矩阵快速幂优化一下就做完了.

E. Inverted World

考虑有 $i=j^{k/j}$, $j$ 要能开若干次方是一个很强的限制, 设 $g=\gcd(k, j)$, 则 $j$ 要能开 $j/g$ 次方, 对 $j/g$:

若 $j/g=1, j=g$, 问题变成 $i=j^{k’}$, 限制题目 $i, k’j\le n$ 的限制, 显然除了 $j=1$ 只有 $\log n$ 段不同的 $k’$, 直接做就行了.

若 $j/g=2, i=j^{\frac{k’}{2}}$, 要求 $k’$ 是奇数和范围限制, 仍然枚举 $k’$ 计算.

否则 $j/g\ge 3$, 则 $j\le n^{\frac13}$, 那么枚举 $j/g$ 和 $j$(总共不到 $n\ln n$, 因为有大量 $j$ 不合法), 确定 $j’=j^{\frac{g}{j/g}}$, $k’$ 要满足 ${j’}^{k’}\le n$, $\gcd(k’, j/g)=1$, $k’, j/g$ 都很小, 可以预处理后快速计算.

然后实际上枚举 $d=j/g$ 和 $j$ 不是 $n\ln n$ 因为还有 $j^{1/d}$ 是整数的限制.

[ARC076F] Exhausted?

相当于求人到椅子的最大匹配. 每个人 $i$ 可以匹配的是一个前缀 $[1, l_i]$ 加一个后缀 $[r_i, m]$.

考虑Hall定理, 我们要选一个集合最小化连向的前缀并连上的后缀.

枚举一个前缀位置 $p$, 则所有 $l_i>p$ 的 $i$ 都不能选, 此时以 $s$ 为后缀就把所有 $r_i\ge s$ 的都选上最优, 那么从小到大扫描 $p$, 不断加入区间 $[l, r]$, 用线段树维护以 $s$ 为后缀的答案即可.

另一个做法是贪心, 考虑按 $l_i$ 从小到大扫人, 如果能匹配就匹配, 否则必须有一个人去右边匹配, 把左边 $r$ 最小的拿出来让他去右边匹配即可.

CF725F Family Photos

考虑如果没有照片对中必须先选第一个的限制, 那么选一个会获得 $a_i$, 不选会损失 $b_i$, 可以A选获得 $a_i+b_i$, B选获得 $0$(实际上是不让A选), 那么方法是按照 $a_i+b_i$ 从大到小排序, 两人都从前往后选.

注意到若 $a_1+b_1>a_2+b_2$ 那么限制已经天然满足了会先选 $1$, 考虑如果 $a_1+b_1<a_2+b_2$, 那么后选这一对的人可以获得 $a_2+b_2$, 如果当前先手选它, 后手立刻选这一对的第二个, 其他位置和先后手都不会变, 那么先手先执行在剩下位置执行的操作是不劣的; 如果先手选它后手不选第二个说明其他地方有收益更高的先手也不应该选这个位置.

如果一个位置我们不选应该获得 $b_i$(一开始强制损失的值). 那么讨论 $a_1+b_1<a_2+b_2$ 的对, 现在轮到 A(选完所有一定选的一定轮到A), 如果它不选第一个而B选了肯定获得 $a_2+b_2$, 如果两人都不选获得 $b_1+b_2$, 那么若 $a_1+b_1<b_1+b_2$, A 不会选这个对.

同理有对B, 不选A获得 $b_1+b_2$, 选了A获得 $a_2+b_2$, 则当 $b_1+b_2<a_2+b_2$ 时不会选这个对. 如果这个和上面的同时发生那么谁也不选它.

于是就分析完了. 感觉重点在, 抛去限制后, 每个对是相对独立的, 可以分析在A干的合理的情况下B会跟着A选这件事, 使得只要考虑一对.

[AGC023F] 01 on Tree

考虑如果一个位置是 $0$, 它应该在父亲被删掉的时候立刻删掉, 于是把它和父亲合并. 那么如果一个位置一定在父亲选后的下一次操作被选就可以把它和父亲合并. 设每个点 $u$ 有 $c_{u, 0}$ 个 $0$ 和 $c_{u, 1}$ 个 $1$.

考虑现在选完一个点, 接下来可以选 $u, v$, 那么 $c_{u, 1}c_{v, 0}<c_{v, 1}c_{u, 0}$ 显然交换时贡献变小. 应该把 $u$ 放在前面, 于是 $\dfrac{c_{u, 1}}{c_{u, 0}}$ 最小的点应该紧接着自己的父亲被选.

重点是紧接着父亲被选的合并, 以及只和点对自身, 相对位置先关贡献的邻项交换.

[AGC007F] Shik and Copying String

显然 $s_0$ 的每个字符 $s_{0, i}$ 可能扩展成一个区间 $[l_i, r_i]$, 满足 $l_i\ge i$. 同时 $[l_i, r_i]$ 是关于 $i$ 是有序的. 满足以上条件则合法.

而这个过程可以用折线描述, 每个 $s_{0, i}$ 形成从 $s_0$ 到 $t$ 的路径, 一条路径左右两侧, 不跨过下一条路径的点都可能是 $s_{0, i}$, 不难发现最优解下每个点都尽力往右跑直到到达自己目标区间的左端点.

用队列维护所有转折点(即每行折线上的第一个点), 那么发现第 $i$ 条折线在第 $j$ 行的转折点是第 $i+1$ 条折线在第 $j-1$ 行的转折点向左下移动一格. 于是只要每次删掉已经到达目的地的点, 平移一下即可维护.

复杂度线性.

P5912 [POI2004] JAS

同时是 [AGC009D] Uninity

显然要求深度最浅的一棵点分树.

考虑设每个点的子树高度为 $h_i$, 那么 $\forall h_i=h_j, \exists k, h_k>h_i, h_k>h_j$, 即 $k$ 要能把 $h$ 相等的点划分到两棵子树.

考虑现在一个子树 $u$, 设 $S_u$ 表示所有值 $v$ 构成的集合, 其中 $v$ 满足存在一个 $h_k=v$, 使得 $k\to u$ 路径上不存在 $h_w>h_k$. 那么现在合并儿子们到点 $u$, 那么如果存在两个儿子 $s_1, s_2$, $x\in S_{s_1}\cap S_{s_2}$, 则 $h_u$ 要大于 $x$. 同时如果 $h_u$ 是某个 $S$ 中的元素也不行. 就可以推出 $h_u$. 而 $S_u$ 就是所有 $S$ 和 ${h_u}$ 并起来, 去掉比 $h_u$ 小的元素.

复杂度 $O(n\log n)$, 可以用位运算压到 $O(n)$.

[think] 感觉把点分树转化成对 $h$ 的限制很厉害, 感觉把限制拆成很多这样更小的限制让它变得更局部了.

AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift

感觉很困难, 做法是把当前问题变成有一个串的多重集 $M$, 拼成 $f(S)$ 最大的 $S$, 那么每次应该拿出 $M$ 中最小和最大的字符串 $m_1, m_k$, 把 $m_k+m_1$ 放回 $M$.

显然如果 $M$ 中元素各不相同最好的方式就是 $m_1+m_k+m_{k-1}\ldots m_2$, 然后现在有若干个 $m_1$, 每个都会作为一个起点, 容易发现按照上面的做法 $M$ 中最多有 $3$ 种不同的元素 $A, B, C$, 设分别有 $a, b, c$ 个.

如果 $a<c$, 能拼成 $AC$ 是显然优的.

如果 $a<b+c$, $f(S)$ 以 $AB$ 开头, 应该得到 $AB, AC, B$, 考虑如果存在一个 $C$ 没有这时拼上得到 $(AB, AC, B, C)$, 那么在以后某时刻终于 $c>a$, 让我们留的 $C$ 派上用场, 我们一开始用这些 $c$ 在很早以前把这些 $a$ 干掉就很优.

对 $a>b+c$, 变成 $(A, AB, AC)$ 同理.

P4364 [九省联考 2018] IIIDX

我们可以先建一棵树, 若 $i$ 解锁 $j$ 则 $i$ 是 $j$ 的父亲, 一个点的所有儿子按编号从左到右排, 限制就是要求儿子大于父亲, 求字典序(bfs序字典序)最大的解.

在 $d$ 不重复的时候是容易做的, 把权值从大到小排序, 然后每个儿子子树分配一个区间的权值递归下去.

但如果 $d$ 存在重复, 那么现在第一个儿子填什么仍然确定, 然后应该优先把这个值的全都丢进子树, 留下最大的若干个? 但这是不对的, 确定这个儿子的时候, 也有可能留下的若干个没有影响这个点的兄弟, 而到了兄弟的儿子中, 此时不如给当前儿子的儿子了.

考虑 $1\ldots n$ 逐位确定, 那么要保证当前点 $u$ 填完之后还合法, 只要保证还能有 $siz_u-1$ 个不小于当前值的数, 相当于存在一个每个 $u$ 匹配 $siz_u-1$ 的匹配

这个可以hall定理啊, 就成了要求对所有后缀, 后缀内被填了的 $u$ 的 $siz$ 之和不大于后缀长度了.

然后到一个点的时候要把它父亲的限制修正(不是要求 $fa_u$ 有 $siz_{fa_u}$ 个匹配, 要让 $u$ 子树内的匹配 $u$).

复杂度 $n\log n$.

[AGC010E] Rearranging

考虑如果第一个人已经确定了序列,若$i,j$不互质,那么我们不能交换它们,$i$在最终的序列一定在$j$左侧,对所有不互质的点对建条件就是完备的,得到一个 DAG,而最终序列就是DAG的拓扑序,只要在拓扑序的时候把队列换成堆就可以求字典序最大的拓扑序,这是对一个已经确定的序列的做法.

现在序列还没确定,那么把所有不互质的点对拿出来连边得到若干连通块,对每个连通块要最小化它的字典序,这里就贪心的看每个点,让最小的连到自己的定向到自己,得到一棵树即可,容易发现是最优的.

CF526G Spiders Evil Plan

以$x$为根,相当于选$2y$或$2y-1$($x$度数为$1$)个叶子

然后贡献是一个链并的形式不好求,注意到对$x$的一个$u$的子树内若存在叶子被选,则$u$所在长链叶子应该被选.考虑若没选而选了另一部分进行一些替换必然可以更好.于是可以让每个叶子的贡献是自己到长链头的父亲这段的边权和.

但不能对每个$x$跑一遍长剖,考虑经过$x$的最长链一定一端是直径端点,考虑以直径端点为$x$做,此时如果包含$x$可以直接输出,否则要么删掉贡献最小的叶子加入$x$子树中的,要么找到经过离$x$最近的,有叶子被选的祖先的一条路径,把后面的部分改成选到$x$子树中深度最大的点. 就做完了.

[think] 发现关于长链选叶子的单调性简化贡献计算,调整满足题目限制

CF1477E Nezzar and Tournaments

考虑如果没有这个取max,实际上$v_i=c_i+k-c_1$,毕竟每次加入的是差分,那么我们设$w_i=v_i-c_i$,只要考虑两个数列的$w$产生的差值,有$w_i=\max(0,w_{i-1}+c_i)-c_i=\max(-c_i,w_{i-1})$,$w_0=k-c_1$.于是$w_i=\max(k-c_1,\max_{j\le i} -c_j)$.

显然越靠后$w$越大,所以你会想到$b$降序排列后$a$升序排列,但$c_1$是一个特殊元素.

考虑若$c_1$在$b$中无疑让$w_1$变大,而不会改变$w_{m+1}$以后的东西(始终是对前面这些取$min$),一定不优.

那么如果把$a$中元素移过来,我们把$\max_{j\le i} -c_j$一定是一段上升然后后面不变,而$k-c_1$是一条直线,容易发现当直线没高出折线最大值时越往下越好,则实际上只有$a_{min},a_{max}$可能成为答案.

这样一来只要能快速求值,发现是简单线段树问题.

CF1637H Minimize Inversions Number

考虑选一个数$p_i$移动到最前面,$\Delta ans=(\sum_{j<i}[p_j>p_i]+\sum_{j>i}[p_j<p_i])-(\sum_{j<i}[p_j<p_i]+\sum_{j>i}[p_j>p_i])=d_i$

我们希望贡献尽量局部,对于一个子序列$p_{q_1}\ldots p_{q_k}$,得到$\Delta ans=\sum_i d_{q_i} - \sum_i \sum_{j<i} [p_{q_i}>p_{q_j}] + \sum_i \sum_{j<i} [p_{q_i}<p_{q_j}] = \sum_i d_{q_i} + \binom{k}{2} - 2\mathrm{inversion_count}({q_1\ldots q_k})$

不知道怎么发现一个性质,一定存在一种不劣方案使得不存在逆序对$(i,j),i<j$,$i$在$q$中而$j$不在.

考虑选择$j-i$最小的一对非法逆序对,则把$j$替换成$i$看贡献变化,会发现一定是负的.

于是$\mathrm{inversion_count}({q})=\sum_i \sum_{j>i} [p_{q_j}<p_{q_i}]=\sum_i\sum_{j>q_i} [p_j<p_{q_i}]$.

这样每个数贡献独立,排个序从大到小选就行了.复杂度$n\log n$

[AGC023D]回家

乍一看很吓人的东西,考虑一开始的情况很复杂,分析最终情况:

最后一个回家的肯定来自$x_1$或$x_n$,若$x_1>x_n$,则会先走到$x_1$再走到$x_n$,此时$x_n$的人只希望$x_1$早点回家,所以可以把它们合并,递归下去.

做完了?!

P6168 [IOI2016] railroad

容易想到一个图论模型,对速度离散化,每个速度$v_i$建一个点,$v_i \stackrel{0}{\longrightarrow} v_{i+1},v_{i+1} \stackrel{v_{i+1}-v_i}{\longrightarrow} v_i$,对每个特殊路段建 $s_i \stackrel{0}{\longrightarrow} t_i$,则要求把所有特殊路段的边走一遍.问题是我们可能多走很多两个速度之间的没用边.

考虑什么时候两个速度之间应该有一条边,如果对于$v_i \leftrightarrow v_{i+1}$有$a$条从小的连到大的跨过它的特殊路段,$b$条从大连到小的特殊路段,那么若$a>b$需要减速方向走$a-b$次,$a<b$需要加速方向走$b-a$次.如果$a=b=0$需要走一次.

发现我们的建边方式会平衡入度和出度,于是做完了.

[AGC041D] Problem Scores

显然对于任意$k$,$S$是$a_{n-k+1}\ldots a_n$,$T$是$a_1\ldots a_{k+1}$.自然想到设前缀和$pre_n$,后缀和$suc_n$,则$sum(S)-sum(T)=pre_{k+1}-suc_{k}=s_k$.

注意到$s_k-s_{k-1}=a_{k+1}-a_{n-k}$,又因为$a$是递增的,所以这个东西在$k=\lceil \dfrac{n-1}{2} \rceil$的时候最小,设为$K$,只要满足此刻的限制.

[think] 不知道干什么就把东西列出来,试试差分,前缀和.

此时如果$n$是奇数,则每个数恰属于$S$或$T$,如果是偶数则有一个数不在集合中.

考虑设$b_i=a_i-a_{i-1}$,每个位置有一个贡献系数$c_i$,要求$\sum_i b_i\le n,\sum_i b_ic_i\le 0$.这是一个二维的背包,不好做.

对$n$为奇数有$c=1,0,1,-2\ldots -k+1,-k,-k+1\ldots -1$,对$n$为偶数$c=1,0,1,-2\ldots -k+1,-k,-k+1\ldots -1$,拿出贡献系数为$1$的$b_1$,根据两个限制有$b_1\in [\sum_i b_ic_i,n-\sum_i b_i]$,于是一种方案的贡献是$n-\sum_i b_i(c_i+1)$,于是对$c_i+1$做完全背包即可.

[trick] 拿出背包中的一个元素让二维dp转化成一维dp

[AGC003F] Fraction of Fractal

分类讨论,如果把两个原图横/竖放在一起都不连通,显然答案是$cnt^k$,$cnt$表示黑格数,如果均连通是$1$,现在考虑横着连通竖着不连通.

考虑左右有$c$个格子相连,迭代$k$次后会变成$c^k$个.

再考虑迭代$k$次我们可以看成把原图每个格子换成迭代$k-1$次的.因为纵向不连通所以每行可以单独看.设$f_i$表示迭代$i$次后的答案,对于一行里长$a$的极长连续黑格子段,换掉$k-1$后显然得到$af_{k-1}-c^{k-1}$.

那就做完了啊,统计每行连续段长度和为$A$,数量为$B$,$f_i=Af_{i-1}-Bp^{k-1}$,矩阵快速幂或者生成函数都行.

[AGC040D] Balance Beam

一定是一个前缀$[1,x]$可以追上.

所以我们要最大化这个前缀$x$,拆成$\lfloor x\rfloor$和${x}$,第一部分就是把所有元素划分成$S_1,S_2,S_3$(能追上的前缀,不能追上的前缀,追上后没啥用的),使得$\sum_{i\in S_2} (B_i-A_i)-\sum_{i\in S_1}A_i\ge 0$,最大化$\vert S_1\vert$.而确定第一部分之后第二部分可以快速计算.

那么一个元素进入$S_1$贡献$-A_i$,进入$S_2$贡献$B_i-A_i$,我们先把所有$B_i-A_i>0$的元素放进$S_2$,再尝试最大化$S_1$,则$S_2$的元素进入$S_1$会贡献$-B_i$,其他贡献$-A_i$,排序一下从小到大选即可.

枚举$x$到底落在哪块上,上面的排序选值可以预处理后二分快速计算.

P8500 [NOI2022] 冒泡排序

注意到显然值可以离散化.注意到如果$i,j$的值可以交换且$a_i>a_j$,交换后一定更优.

对性质B,一些位置已经确定而另一些位置任意,因为上面的交换性质,我们自己填的数内部一定不会有逆序对,递增,则只考虑和其他数的贡献,让每个数填最小化和其他数的贡献的数,这样也能保证你填的数递增,用线段树优化复杂度$n\log n$.

对性质C,因为可以交换而区间内一定有一个最小值,所以一定填在第一个位置,然后变成每个位置有一个要限制$>lim_i$,此时既有和已经填好的数的贡献又要考虑到还没填的元素和当前元素的贡献,结论是直接贪心最小化和前面的贡献:若当前选择最小化前面的贡献值是$x$,而可以选择更小的数$y$,那么把后面还没填的数中$[x,y]$中的数都改成$y$是没有什么坏处的.

最后对整个问题,每个区间的最小值应该放在能填的最左位置,对最小值相同的区间跑一个线段覆盖贪心即可.

突破口在可以交换,难点在性质C的贪心,需要有充足时间.

P7739 [NOI2021] 密码箱

考虑合并完后若干项得到$\dfrac{a}{b}$,那么套一层后$\dfrac{a’}{b’}=x+\dfrac{b}{a}=\dfrac{b+ax}{a}$.

注意到若$a\bot b$,必然有$\gcd(b+ax,a)=\gcd(a,b)=1$,于是在运算过程中始终是最简分数.

可以把转移写成矩阵,则转移一次就是

$$
\left [a’,b’\right]=\left [a,b\right] \times M_x\
M_x=
\begin{Bmatrix}
x&1\1&0
\end{Bmatrix}
$$

则如果确定$a$,答案可以看成从右往左每次左乘矩阵的连乘积.

我们要能快速维护操作,考虑把操作也写成矩阵,对于W,我们有矩阵
$W=\begin{Bmatrix}1&1\0&1\end{Bmatrix}$使得$WM_x=M_{x+1}$,对于E,对最后一项不为$1$设$H=\begin{Bmatrix}1&-1\0&1\end{Bmatrix}$使得$HM_x=M_{x-1}$,我们要的是$E=M_1M_1H$,否则我们要的是$E’M_1M_x=M_1M_{x+1}$,即$E’M_1=M_1W$,分别计算发现$E=E’=\begin{Bmatrix}2&-1\1&0\end{Bmatrix}$,十分的巧啊.

剩下就是用平衡树维护矩阵乘积支持区间翻转反转单点插入了.

P6775 [NOI2020] 制作菜品

考虑$m\ge n-1$时,每次取出最小的作为这道菜的一部分,如果不够就去拿最大的,显然可以递归到$m-1,n-1$或$m-1,n$.直到$m=1,n\le 2$做完.

那么现在$m=n-2$,考虑若一道菜用了$a,b$两种原料就连边$(a,b)$,则一个连通块必然有$m\ge n-1$.于是$m=n-2$的情况必然有至少两个连通块,且为了保持$m\ge n-2$的性质每个集合都是$m=n-1$,于是必然存在集合$S$使得$\sum_{i\in S} a_i=k\vert S-1\vert$,用bitset优化01背包即可.

P7740 [NOI2021] 机器人游戏

他甚至好心给了样例解释$2$,容易想到基于容斥的暴力,考虑枚举集合$S$计算以$S$中的位置为起点可行的方案数.

那么机器人进行的修改是,把$p+i$处变成$0/1/X_i/1-X_i$之一,我们处理出每个位置可能是哪几种情况,此时每个格子独立,对于一个格子:

同时有$0$和$1$或同时有$X_i$和$1-X_i$,只能为空,有$1$种可能.
同时有$0/1$中一个,$X_i/1-X_i$中的一个,此时只有一种确定的$0/1$或为空,$2$种可能.
否则空,$0/1$有$3$种可能.

复杂度是$nm2^n$.

考虑不枚举而使用dp,设$f_{i,S}$表示考虑前$i$个格子,其中$S$的位置可以作为起点,每次转移时枚举当前位置是否能作为起点并乘上方案数和容斥系数.第$i$个机器人超过位置$l_i$启动会爆炸,设$L=\max l_i$,复杂度是$n^2m2^L$,而我们容斥的做法复杂度是$nm2^{n-L}$,结合就能做到$nm2^{n/2}$

然后用bitset优化除掉一个$w$即可.

P5469 [NOI2019] 机器人

考虑dp,显然两个机器人分别走到左侧第一个大于它的位置和右侧第一个大于等于它的位置.这是一个比较有局部性的东西,$[l,r]$这个子问题,设$x=\max_{i\in [l,r]} h_i$,要求$h_{l-1}>x,h_{r+1}\ge x$,于是设$f_{l,r,x}$表示这个子问题对应方案数.那么考虑最后一个为$x$的位置$p$,分裂成$\sum_{y\le x,z\lt x} f_{l,p-1,y}f_{p+1,r,z}$,然后$p$要满足到$l,r$的距离差不大.复杂度是$n^2V$.但是这个$p$限制很严,所以有用的区间不多.

考虑如果没有$h_i\in [A_i,B_i]$的限制,那么容易发现$f_{l,r,x}$是关于$x$的$O(r-l)$次函数,拉插.

那么现在有限制,把限制离散化,容易发现$f_{l,r,x}$在每个区间内是关于$x$的$O(r-l)$次函数,复杂度是$n^4$.

P5472 [NOI2019] 斗主地

考虑每次重排时如果第$i$个来自第一堆$b_i=0$,否则$b_i=1$,则每个$01$序列$b$的概率是相等的.那么设$f_{i,j}$表示$i$次重排之后第$j$个的期望:

那么有

$$
f_{i,j}=\dfrac{1}{\binom n{a_i}}\sum_{k\le a_i} f_{i-1,k}\binom{j-1}{k-1}\binom{n-j}{a_i-k}+\sum_{k\le n-a_i}f_{i-1,a_i+k} \binom{j-1}{k-1}\binom{n-j}{n-a_i-k}
$$

但这个很难办啊,必须得有点性质,比如$f$是个多项式啥的,因为这里是组合数,先把多项式化成$F(x)=\sum_i c_i\binom{x-1}{i}$的形式,代入$f_{i-1,k}=\binom kc$,这里只考虑第一个求和号:

$$
\sum_{k\le a_i} \binom{k-1}{c}\binom{j-1}{k-1}\binom{n-j}{a_i-k}\
=\binom{j-1}{c}\sum_{k\le a_i} \binom{j-1-c}{k-1-c}\binom{n-j}{a_i-k}\
=\binom{j-1}{c}\binom{n-1-c}{a_i-1-c}
$$

是关于$j$的$c$次多项式!所以结论是若$f_{i-1}$是$k$次多项式则$f_i$也是,我们只要挑$3$个点值计算就做完了.

[AGC031D] A Sequence of Permutations

找规律题

[note] 别忘了排列复合的形式是$p=a\circ b\Leftrightarrow p_i=a_{b_i}$

所以题目这个是$f(p,q)=qp^{-1}$.找规律:

$$
\begin{gathered}
a_1=p\
a_2=q\
a_3=qp^{-1}\
a_4=qp^{-1}q^{-1}\
a_5=qp^{-1}q^{-1}pq^{-1}\
a_6=qp^{-1}q^{-1}ppq^{-1}\
a_7=qp^{-1}q^{-1}pqpq^{-1}\
a_8=qp^{-1}q^{-1}pqp^{-1}qpq^{-1}
\end{gathered}
$$

变换是,把$p\to q,p^{-1}\to q^{-1},q\to qp^{-1},q^{-1}\to pq^{-1}$.

且注意到$P=qp^{-1}q^{-1}p$变成自身,$P^{-1}=p^{-1}qpq^{-1}$,发现结论是$a_n=Pa_{n-6}P^{-1}$

[ARC144D] AND OR Equation

显然可以变成集合$a_S+a_T=a_{S\cap T}+a_{S\cup T}$,令$T={i},i\notin S$,有$a_S+a_=a_{S\cup {i}}+a_{\varnothing}$,于是一个集合的值是$\sum_{i\in S} a_i-(\vert S\vert-1)a_\varnothing$,令$v_i=a_i-a_\varnothing$,我们去数$(v,a_0)$满足$a_0+\sum_i w_i$

而要满足值域限制,即$a_0+\sum_i w_i[w_i>0]\le k,a_0+\sum_i w_i[w_i<0]\ge 0$,$a_0$的取值范围是$k+1-\sum_i \vert w_i\vert$,那直接GF:

$$
\sum_{i=0}^k (k+1-i)[x^i] (-1+2\sum_{j\ge 0} x^j)^n
$$

复杂度$O(n)$.

ZR Day3 A. d

容易发现关键在长$2$的黑色方块,考虑一个方案方案是否可见,从上往下扫,如果遇到一个长奇数的黑色短就表明必须有一个新的塔,于是dp,记录当前一共有多少塔,黑色/非黑色方块用了多少,当前高度,就做完了.

[ABC260Ex] Colorfulness

球是区分的,设第$i$种球有$c_i$个,$a_i$序列乘$\prod_i c_i$就是球的序列.

先考虑怎么计算分数为$x$的方案数$f_x$,设钦定有$y$个相邻值相同的方案数为$g_y$,第$i$种球有$b_i$个相邻对($\sum_i b_i=y$),则方案数是

$$
\begin{gathered}
\binom{n-\sum_i b_i}{c_1-b_1,c_2-b_2\ldots c_m-b_m}\prod_i \binom{b_i+c_i-2}{b_i}\
=(n-y)!\prod_i \dfrac{1}{(c_i-b_i)!}\binom{b_i+c_i-2}{b_i}
\end{gathered}
$$

于是设一个颜色的GF是$F_i(z)=\sum_j \dfrac{1}{(c_i-j)!}\binom{c_i-2+j}{j}z^j$就有$g_y=z^y!\prod_i F_i(z)$.分治NTT.

然后二项式反演也是NTT求得$f$,接下来要求

$$
\sum_i f_ii^k=[x^k](\sum_i f_ix^i)\circ e^x
$$

于是复合$e^x$即可.也是分治NTT.

P10611 故事结局

考虑对修改操作颜色段均摊,每个颜色段存在时间是一个区间,线段树分治,可以变成横向线段取max矩形max.

对线段树分治的每个节点,把它包含的所有询问和修改拿出来,那么容易发现这个总和是$q\log q$的很好.

于是对平面用横线分治,把每个4side矩形拆成贴着横线的两个3side矩形(rprmq的trick)然后扫描线,就是简单的区间checkmax区间max问题,复杂度是修改3log查询2log(查询只会在一层被遍历,而修改每层都有)

或者也可以换个方向分治问题变成单点checkmax,区间历史max,全局加,都不太可优化.

然后这题正解其实是考虑树套树,外层行内层列,然后我们对外层树的叶子修改完了,发现可以在外层pushup,因为我们可以只pushup在内层修改过的点,复杂度就对了.

需要离线对外层逐层处理.

JOI Open 2024 Examination2

第一步肯定是直接建表达式树,问题变成给定一棵二叉树,每个点上标着|,&,^之一,叶子是$x$是否大于某值.

那你直接扫$x$,叶子会逐个由$0$到$1$,写个ddp就行了,复杂度$n\log n$.

或者你考虑每个叶子是一个分两段的函数,每次启发式合并两个儿子的函数得到当前点的函数,这个感觉更难写一点,复杂度相同.

JOI Open 2024 Heat

有一个长$L$的链,第$i$条边连接$i,i+1$,每个点有容量$c_i$,$n$次在一条边$x_i$上放一个球,你需要把球放到这条边的剩余容量不为$0$的一个端点并消耗$1$容量,两边都满了扔掉,求扔掉的最大数量.

$L,n\le 8000$.

考虑一个前缀$i$个点,$i-1$条边的子问题,我们需要确定:第$i$个点最后的容量$j$和第$i$个点获得的球的最大编号$k$,以及第$i-1$条边是否扔了东西$w=0/1$,现在分配第$i$条边上的球,则分成$A,B,C$三个集合分别是到$i$的,到$i+1$的和扔掉的.要满足:

$\vert A\vert\le j$,若$w=1$则$\vert A\vert=j$.
$\vert B\vert\le c_{i+1}$
若$\vert A\vert \ne j$,$C=\varnothing$.
$\min_{i\in C} t_i>\max(k,\max_{j\in B} t_j)$

我们希望转移到的$k$尽可能小,所以元素优先放$B$,然后放$A$,最后放$C$,只要确定放了$B$的元素数,剩下的就确定了,转移可以做到$O(1)$,注意到$j$这一维是只要到$i$这条边上的人数的,所以总复杂度是$n^2$.

JOI Open 2024 Library3

交互题,存在一个排列$p_n$,你每次可以询问一个排列$q_n$,获得按照以下策略执行的步数:若$p\ne q$,设$x$为最小的数满足$p_x\ne q_x$,$y$满足$q_y=p_x$,交换$x,y$.要求你确定排列$p$.

$n\le 500$,你可以问$5000$次.

考虑你实际上是在问什么,对于一个长$l$的置换环需要$l-1$次,所以我们可以确定$a=q^{-1}\circ p$的环数.

那么询问$q$和$q’$,$q’$为$q$交换$q_i,q_j$得到的排列,就可以确定$a$中$i,j$是否在同一个环中,因为若在一个环中会分裂,否则会合并,那么不断分裂到最后有$n$个环就得到答案,可以假设现在$1\ldots i$在不同的环中,加入一个$i+1$,只要把它和前$i$个都问一遍,就能保证$1\ldots i+1$在不同的环中.复杂度$n^2$.

考虑优化,看起来像个$n\log n$的东西,现在假设我们确定$1\ldots i$在不同的环中,显然$i+1$和前面的元素中最多一个在一个环,注意我们可以把若干元素合并到一个环,然后问它们和$i+1$是否是一个环,就可以二分了.复杂度$n\log n$.

NowCoder 某数数

数有多少个$n$个点DAG满足每个点出发的最长路等于SG值.

枚举扫描线方向,应该每次加一层叶子,把新的叶子和前面的点归并,前面每个点要连到这层的点至少一个.

剩下的比较简单了,相当于从后往前,每次往前追加一个新点/前面层点,dp预处理即可.

复杂度$n^2$