task16

[TOC]

有人问了我题号后面的 emoji 是啥意思，大概就是想打了就打了，纯属主观判断，大致打的时候想法是这样的：

⭐：有一步比较巧妙/我很喜欢的想法的

✔️：经过一些推导可以慢慢得出来的，或者至少需要做一会的题，我还比较喜欢的

✨：纯魔法题，我无法理解这是咋来的

1. THUPC2025 - I’m Here [E] ✔️

题面

给定一棵 $n$ 个点的有根树，保证 $1,2,\cdots,n$ 组成了一个合法的 dfs 序

第 $i$ 轮你可以进行如下操作：

选择一个还未被删除的点，将其子树中所有节点删除

第 $i$ 轮结束后，如果编号为 $n-i+1$ 的点还存在，那么它会被删除

对 $k=1,2,\cdots,n$，求 $k$ 轮之后将整棵树删空的方案数，对 $998244353$ 取模

$1\le n\le80$

题解

Sol

对于一个根，我们考虑其儿子的情况

设其 dfn 最大的子树大小为 $siz_1$，选了 $c_1$ 次操作，考虑这会对其它子树的操作产生什么影响

可以发现几乎没有什么影响，dfn 第二大的子树需要第 $i$ 个点在 $i$ 时刻及之前选，其中 $i\in[siz_1+1,siz_2]$，也就是说前面选的是哪 $c_1$ 次并不会改变选择数，我们一定是恰好有 $siz_1-c_1$ 的时间是可以选的

一般化一下，此时我们一棵子树的问题就是，前面有 $\sum siz-\sum c$ 的时间是可以随便选的，在这个时间之后，每一个时刻 dfn 最大的节点会被删除

但是我们还需要保证子节点的删除时刻小于父节点，因此我们需要再记一个变量，表示有多少时刻是可用的

最后我们的状态就是 $dp_{u,i,tl,tr}$，表示 $u$ 的子树内选了 $i$ 个点，现在这棵子树会从第 $tl+1$ 时刻开始每次删 dfn 最大的点，要求我们选的 $i$ 个点互不相同且时间戳均 $\le tr$（不要求时间戳连续）的方案数

转移先枚举 $tl,tr$，然后就是树形背包的复杂度，总复杂度 $O(n^4)$

2. QOJ8329 - Excuse [E]

题面

给定 $n$，重复如下操作 $n$ 次生成 $a$ 序列：

抛一个均匀硬币，将第一次正面朝上前背面朝上的次数加入到 $a$ 序列末尾

求 $\text{mex}(a)$ 的期望，对 $998244353$ 取模

$1\le n\le10^5$

题解

Sol

考虑首先列出一个式子，不妨求 $\text{mex}\ge i$ 的概率，那么就是要求 $0,1,\cdots,i-1$ 都在序列中出现至少一次

而计算这个我们可以使用容斥，对每个位置我们认为其为 $0,1,\cdots,i-1,\times$ 中的一个，要求 $0,1,\cdots,i-1$ 都没选过至少一次，系数为 $(-1)^{选的个数+i}$

这个写成生成函数即为 $\prod_{j=1}^i(e^{x/2^j}-1)$，而我们要求的就是所有这样生成函数之和，最后再卷上一个 $e$，其 $n$ 次项系数乘上 $n!$

计算这个可以考虑倍增，每次就是复合上一个 $\frac1{2^w}x$，这是可以做到的

复杂度 $O(n\log^2n)$

3. CF1326F2 - Wise Men [K] ⭐

题面

给定一个 $n$ 个点的完全无向图，每条边有边权 0 或 1

对每个长为 $n-1$ 的 01 串，求有多少哈密顿路径使得路径上的权值按顺序排序得到的是这个串

$2\le n\le18$

题解

Sol

wow.

直接存 01 串非常不好做，因此我们可以考虑转变一下求的东西。

如果我们就选择一些位置钦定它们是 1，其余位置随意，那么我们是可以通过一次差分求出最后的答案的

而这个转化后的问题就相对好做一些了，我们相当于就是将一些 1 链拼起来，每种长度的链可以提前 dp 出来，存在一个 $fc_{c,S}$ 里，表示长为 $c$，且经过的点集为 $S$ 的 1 链个数

注意到在这个转化后的问题，我们只关系 1 链长度的可重集，所以实际上不同的问题数量只有分拆数即 $P(n)=385$ 种，对于一个问题我们需要做的就是一个 or 卷积，这个是可以做到 $O(P(n)2^n)$ 的

所以最后总复杂度就是 $O(P(n)2^n+n^22^n)$ 的

4. QOJ2068 - Fast as Ryser [E]

题面

给定一张 $n$ 个点 $m$ 条边的无向图，每个边的权值均为 $c$，求所有匹配的权值乘积之和，对 $10^9+7$ 取模

$1\le n\le36$

题解

Sol

见过这个科技。

考虑对考虑把 $n$ 补到偶数，然后在每个 $2i$ 和 $2i+1$ 之间连一条辅助边，这样我们一共会有 $n/2$ 条辅助边，称为 $n/2$ 组

而一个匹配就是一种选一些边，和这些辅助边一起将所有点串成了一些环和链

那么我们求出组的集合组成一个环或者一个链的权值和，最后用集合幂级数 exp 即可

而这个是容易 dp 求出的

因此总复杂度 $O(2^{n/2}n^2)$

5. ATxmascon22F - Fast as Fast as Ryser [K]

题面

给定一张 $n$ 个点 $m$ 条边的无向图，对每个 $k=0,1,\cdots,n/2$ 求有多少大小为 $k$ 条边的匹配，对 $2^{64}$ 取模

$1\le n\le40$

题解

Sol

别集合幂级数了。

集合幂级数也可以从上面的东西扩展出来一个做法，但是我不想写。

考虑假设我们不需要记匹配的边数，那么有一个做法是我们每次选择一条包含最大未选点的环或者链，然后每次在当前结构的末尾加一个点

具体地，设当前访问过的组集合为 $S$，$S$ 中最大未选组为 $u$，我们定义如下规则：

额外记一个状态变量，状态变量的值为 $0/1/2$
$0$ 状态表示我们从 $u$ 开始要走一个环，已经加入环上的组，除了 $u$ 都已经在 $S$ 内了，我们需要走若干个组之后走回 $u$，这种可以 dp 解决
$1/2$ 状态表示我们从某个点开始走一条链，且当前有没有已经经过 $u$，这种也可以 dp 解决

那么这个复杂度是 $O(2^nn^2)$ 的

注意到如果我们再记一个个数 $j$，表示当前选过多少条链，那么注意到一个 $j$ 的状态，其 $S$ 的最大的 $j$ 组一定都被选过了，也就是说我们最后的状态数是 $\sum 2^ii^2(n-i)$ 的，因此总复杂度为 $O(2^nn^2)$

6. QOJ4983 - Imbalance [K] ✔️

题面

一个长为 $n$ 的 01 串，其中一个长度为 $m$ 的前缀已知，求有多少 01 串满足任意长为 $k$ 的子区间都满足 01 个数不相等，对 $998244353$ 取模

$1\le m+1\le k\le n\le114$，保证 $k$ 为偶数

题解

Sol

首先有一种显然的暴力方法是 $O(n2^k)$ 的，我们只要记一下前 $k-1$ 位的状态，新加入一个位判断是否满足条件即可

尝试做一下可以发现这个题不太好多项式复杂度，而这个限制相当于任意 $s_i\neq s_{i+k}$，因此我们可以考虑列成矩阵，然后数据分治

那么我们现在就是要解决一个 $\frac nk$ 行的问题，直接暴力可以枚举每一行的开头和结尾，做到 $O(nk^{2(n/k)})$ 之类的复杂度，太高了

考虑提前枚举 $s_0,s_k,s_{2k},\cdots,s_{\lfloor n/k\rfloor k},s_n$，那么我们可以认为我们最后就是要求每个 $(0,s_{ik})$ 要走到 $(k,s_{(i+1)k})$，$(0,s_{\lfloor n/k\rfloor k})$ 走到 $(n\bmod k,s_n)$ 的不交路径数量，这个可以用 lgv 引理求

但是我们还没有解决前缀已知的问题，这个我们可以把 $(m,s_m)$ 平移到 $(0,0)$，然后后面的类似平移，然后把前面路径访问过的点 ban 掉

还有一个问题是此时 lgv 可能算出来一些不对的路径，因为我们的点对还有可能有一些错位匹配也能形成不交路径

这个我们可以把 $(n\bmod k,[>s_n])$ 的点全 ban 掉来处理

那么最后就是 dp 一遍求方案数，然后求一下行列式即可，复杂度 $O((\frac k2)^{n/k+1}(\frac nk)^3)$，写出来是可以跑过 $L>22$ 的，对于 $L\le 22$ 的部分我们跑 $O(n2^k)$ 的暴力。

7. QOJ7932 - AND-OR closure [S]

题面

给定一个大小为 $n$ 的集合 $A$，你需要求出最小的集合 $B$ 使得 $A\subseteq B$，且对于任意两个数 $x,y\in B$，均有 $(x\text{ OR }y),(x\text{ AND }y)\in B$

求最小的 $B$ 的大小

$1\le n\le2\times10^5,0\le a_i<2^{40}$

题解

Sol

$B$ 就是 $A$ 中的元素不断做 $\text{AND}$ 和 $\text{OR}$ 可能得到的所有数

观察一些浅显的性质：如果两个二进制位 $i,j$，满足 $A$ 中包含 $i$ 的数一定都包含 $j$，那么 $B$ 中的元素一定不会出现 $i$ 为 $0$，$j$ 为 $1$ 的数

而我们发现去除掉 $A$ 中全 $1$ 或全 $0$ 的位，然后合并相同的位之后，满足这个条件的数一定是可以生成的

具体地，这个是一张 DAG，我们将其划分成两个点集 $S,T$，使得不存在 $T\rightarrow S$ 的边，最后 $S$ 中的位都为 $1$，$T$ 中的位都为 $0$，我们先把 $A$ 中的数全或在一起得到 $X$，然后每次选择一个 $T$ 中的节点 $u$，将所有不包含 $u$ 这一位的数全或在一起得到 $Y_u$，然后执行 $X\leftarrow X\text{ AND }Y_u$，这样操作之后 $u$ 能到的位会都变成 $0$，其余位都不变

因此我们只需要求 DAG 集合划分的方案数即可，这个我们可以按拓扑序折半，然后枚举前半，对后半进行高维前缀和即可做到 $O(2^{n/2}n)$

8. QOJ7938 - Graph Race [S]

题面

给定一个 $n$ 个点 $m$ 条边的无向图，每个点有属性 $a_i,b_i$，对所有与 $1$ 有连边的点 $v$，求 $\max_{u\neq v}\{a_u-b_u\cdot dis(u,v)\}$

$2\le n\le3\times10^5,1\le m\le3\times10^5$

题解

Sol

建出从 $1$ 出发的最短路 DAG，从 $v$ 出发直接能到的点距离为原来的 $dis-1$，走过一条 $dis_x=dis_y$ 的边能到的点距离为原来的 $dis$，其余点的距离为 $dis+1$

DAG 上 dp 一下即可

复杂度 $O(n+m)$

9. QOJ5166 - 回文匹配 [K]

题面

对于一个字符串 $s$，定义 $P(s)$ 为 $s$ 中所有回文串出现的位置

对于两个字符串 $s,t$，定义 $s$ 和 $t$ 回文匹配当且仅当 $P(s)=P(t)$

给定 $n$ 个字符串 $s_i$，$q$ 次询问，每次给定 $i,j$，求有多少 $s_j$ 的子串和 $s_i$ 回文匹配

两种部分分，第一种部分分每个 $s_i$ 由输入给出，保证 $\sum|s_i|\le5\times10^5$，第二种部分分每个 $s_i$ 定义为之前的某个字符串 $s_{f_i}$ 后面拼上一个字符 $c_i$

$1\le n,q\le5\times10^5$

题解

Sol

这个 $P(s)=P(t)$ 的限制条件太复杂了，我们考虑造一些更简单的限制条件

如果我们能把每个字符串映射成一个序列 $fr$，满足每个字符串的 $fr_i$ 只与前缀 $[1:i]$ 有关，且两个字符串相等当且仅当其 $fr$ 序列相等，那么我们就可以在这个上面建立一些字符串算法的结构

而这里我们可以取 $fr$ 序列为以 $i$ 结尾的最长回文后缀长度，只要说明可以只通过 $fr$ 构造出来 $P$ 集合即可，而这个我们可以归纳，假设我们已经构造出来了长为 $i-1$ 的前缀的 $P$，加入 $fr_i$ 之后我们首先会向 $P$ 中加入这个最长的回文后缀 $[i-fr_i+1,i]$，然后任意更小的回文后缀一定是 $[i-fr_i+1:i]$ 的回文前缀，这个是可以从我们之前的信息定位到的，所以我们可以确定出来 $[1:i]$ 前缀的 $P$

那么我们只要把 $fr$ 序列匹配即可，直接在字符串上做这个询问，我们可以建 ac 自动机，然后离线树状数组处理询问，因此我们也考虑建出这个 $fr$ 的 ac 自动机

直接仿照建 ac 自动机的过程，唯一的区别就是我们现在跳 fail 的时候新加的 $fr$ 会变化，每次需要重新求，因此对于第一种部分分我们直接建 ac 自动机的复杂度就是 $O(\sum |s_i|\log |s_i|)$ 的

第二种部分分限制我们不能均摊建 ac 自动机和回文自动机。

首先解决回文自动机，注意到我们回文自动机在 trie 树上建，和其它串是无关的，因此我们可以 dfs 建树

而 dfs 建树的时候我们需要解决均摊找 fail，也就是不断跳 fail 链，判断前面一个字符是否等于新加的字符，从节点 $u$ 跳到 $fail_u$ 的时候我们一定知道 $fail_u$ 前面的字符，所以我们可以处理出 $lnk(u,c)$ 表示从 $u$ 开始一直跳，直到跳到某个串前面的字符为 $c$ 时跳到的节点，注意这里面不包含 $u$，所以我们需要单独判一下

这个复杂度就是 $O(n|\Sigma|)$，接下来解决 ac 自动机的部分

注意到我们在一个 $fr$ 串后面加一个字符，最多只可能有字符集种新的 $fr$ 的可能，所以我们还是建 trie 图，只不过建 trie 图的过程使用记忆化搜索，即可做到只用求 $n|\Sigma|$ 次 $fr$，即复杂度 $O(n|\Sigma|\log n)$

事实上这个状态数也不超过 $n\log n$，因为我们一个等差数列前面的字符一定是相等的，任意一个点向后加一个字符也最多有 $\log n$ 种情况，所以我们的复杂度实际上可以分析到 $O(n\min(|\Sigma|,\log n)\log n)$

但如果我们对一个节点，直接将其放到到原串中的任意出现位置，然后枚举所有字符在这个位置后面加入得到的 $fr$，以及跳到的节点，将这个 pair 插入到转移里，也可以得到我们想要的值，而对于所有字符一起求我们就可以先倍增到足够小的长度，然后再调用 $lnk$ 数组 $O(1)$ 求出这个位置，因此这样做的复杂度应该是 $O(n\min(|\Sigma|,\log n))$

询问复杂度是 $O(q\log n)$ 的

10. QOJ8703 - 天气预测 [K] ✔️

题面

给定一棵大小为 $n$ 的树，每个节点有一个点权 $a_i$，其中 $a_i$ 以 $p_i$ 的概率为 $1$，以 $(1-p_i)$ 的概率为 $0$

按照如下规则定义 $w_u$：保证树上每个点都有偶数个儿子，对于点 $u$，$w_u$ 定义为所有儿子 $v$ 的 $w_v$ 组成的可重集，并上 $\{a_u\}$ 之后众数的值

$q$ 次修改，每次修改一个位置的 $p_i$，求所有修改前以及每次修改后 $w_1$ 为 $1$ 的概率，对 $998244353$ 取模

$1\le n\le2\times10^5,1\le q\le5\times10^4$

题解

Sol

$q=1$ 已经需要 ntt 了，所以考场上我们已经可以放弃这道题了。

首先考虑菊花怎么做，即只有一层的问题。

此时我们就是需要维护 $n$ 个一次式乘起来的多项式小于等于 $\frac n2$ 的系数之和，并且我们还要支持修改，这个看起来就不是很好做

存在根号做法，但我们有 polylog 的做法。

考虑线段树分治，我们就是在一些区间上插入一个一次式，然后一开始乘上一个 $\frac1{1-x}$，我们就是要求每个线段树上叶子到根路径上所有一次式的乘积的 $\frac n2$ 次项

这个可以在线段树上 dfs，注意到 dfs 到区间 $[L,R]$ 时，我们需要保留的项数是子树内任意一条链上的一次式的个数最大值，那么我们对每一个点考虑，每个点所有一次式到根路径的长度的并的总和是 $O(n+q\log n)$ 的，因此可以做到复杂度 $O((n+q\log n)\log^2n)$，其中 $\log^2$ 是分治 ntt

接下来考虑放到树上做。看起来需要一个动态 dp 之类的东西，使用树剖也可以得到一个 $\log^3$ 的做法，但是这不太好写，我们考虑另一种解决动态 dp 问题的方法

考虑离线下来线段树分治，然后在原树上 dfs，假设我们已经得到了每个儿子 $v$ 的线段树，维护 $v$ 在 $0\sim q$ 时刻答案的连续段，我们想要并上 $u$ 算出 $u$ 在 $0\sim q$ 时刻答案的连续段，可以进行如下过程：

在所有儿子的时间线段树上同时进行线段树合并，如果此时我们发现递归到的节点至多有一个不是叶子，那么我们取这个不是叶子的点，将剩下的点视作对这个点子树的答案进行某种区间修改，打一个懒标记上去

这样我们最后合并出来的线段树上就存下了 $u$ 在 $0\sim q$ 时刻的答案

把这个过程套回来，进一个线段树节点的时候，我们需要保留的项数是当前我们还在合并的不同根的数量，而根据线段树合并的分析，这个就是我们一开始线段树的总结点数，因此是 $O(n+q\log n)$ 的

那么我们的总时间复杂度就是 $O(n\log^2n+q\log^3n)$

11. CF1662J - Training Camp [] ✔️

题面

给定一个 $n\times n$ 的拉丁方 $a$（权值为 $1\sim n$），每个位置额外有一个 01 权值 $c_{i,j}$，你需要选 $n$ 个位置，使得每行每列恰好选了一个位置，并且对于任意没选的位置 $(x,y)$，满足 $a_{x,y}$ 要么大于第 $x$ 行和第 $y$ 列选的两个数，要么小于第 $x$ 行和第 $y$ 列选的两个数

求选的位置的 $c$ 之和的最大值

$1\le n\le128$

题解

Sol

考虑什么样的限制是合法的，那个奇怪的条件没被满足就说明存在一个 $(x,y)$ 使得选的两个数一个大于它一个小于它

如果我们将大于同行同列的，和小于同行同列的分为两个集合，这个就渐渐有割的形状了

我们将同行的点值为 $i$ 的向值为 $i+1$ 的连边，那么最后我们这两个集合应该是被选的点割开的

严谨说明一下：我们要割掉一些点，使得小数与大数不连通，即如果要满足条件，我们的点一定是一个割，如果是割，也一定满足条件

那么我们对 $n\times n$ 种选择分别拆点，然后每个点像同行同列的值域后继连边，$S$ 向所有值为 $1$ 的位置连边，值为 $n$ 的向 $T$ 连边，最后我们需要割掉一些点使得 $S$ 和 $T$ 连通

但我们还没有限制其它东西，比如每行每列选一个，和选的 $c$ 之和最大

这个我们只要给割每个点的代价都加上一个小无穷（ $>n$ ），就限制了这件事情

复杂度是 $n^2$ 个点，$n^2$ 条边，流量 $n^2$ 的网络流

12. ATcf17final I - Full Tournament [E]

题面

有 $2^n$ 个人依次编号为 $1\sim 2^n$ 排成一排，定义如下的竞技过程，将所有人排名：

称一个 $i$ 阶竞技为对排成一排的 $2^i$ 个人进行排名的过程
若 $i=0$，则不会做任何事情，这个人自动排名第一
否则，从左到右每个 $2i-1$ 位置的人会和 $2i$ 位置的人进行比赛，编号小的一方总会获胜，然后胜者进行 $i-1$ 阶竞技决出第 $1,2,\cdots,2^{i-1}$ 名，败者进行 $i-1$ 阶竞技决出第 $2^{i-1}+1,2^{i-1}+2,\cdots,2^i$ 名

现在给定一个排名，其中有些位置被挖去，要求还原任何一个满足条件的 $2^n$ 个人的初始顺序，或者判断无解

$1\le n\le18$

题解

Sol

下面都将下标减 $1$。

我的思路

我一开始做这道题可能想的有点错，后面补充了一下证明。感觉可能并不一定是最简单的思维方式，但是还是放在这里供大家参考。

我们最后需要构造的是初始顺序，一种简单的想法是让初始顺序中胜者一定排在左边。这是一个很美好的想法，但我们需要证明只考虑这种情况就是正确的。

事实上，这确实是正确的，如果我们定义胜者总是排在左边的初始顺序是标准的，那么我们说明任意一种可能得到的排名一定可以被一个标准的初始顺序得到，证明如下：

我们对一个排名，取任意能生成它的初始顺序，我们的目标是将其调整为标准的，设这个初始顺序第一次出现左边输给右边是在第 $i$ 层

此时所有比赛一定形如：将这个长为 $2^n$ 的序列分成长为 $2^i$ 的块，每块内称左边的 $2^{i-1}$ 个元素组成的序列为 $a$，右边的 $2^{i-1}$ 个元素组成的序列为 $b$，由于下面的层都是左边的人胜，所以第 $i$ 层的所有比赛就是 $a$ 和 $b$ 对位比赛

此时我们进行如下调整：对于所有 $a_j>b_j$ 的位置 $j$，交换 $a_j$ 和 $b_j$

这样调整后，如果前 $i-1$ 层仍然满足条件，则可以说明我们 $i$ 步操作后生成的集合一样，后面生成的排名应该也不变

而前 $i-1$ 层确实是满足条件的，交换完产生的两个序列分别为 $\min(a_j,b_j)$ 和 $\max(a_j,b_j)$，而在 $a_j\ge a_k(k\subseteq j),b_j\ge b_k(k\subseteq j)$ 的条件下，不难发现一定有 $\min(a_j,b_j)\ge\min(a_k,b_k)(k\subseteq j)$，$\max$ 同理

那么我们就成功地把任意一种初始顺序调整为了标准顺序。

而手玩容易发现一个标准顺序 $p$ 生成的排名一定就是 $p$ 做蝴蝶变换的结果（二进制位翻转）

那么我们首先对一开始的排名做一个蝴蝶变换，剩下的条件就是 $a_i\le a_{i\text{ OR } 2^j}$，可以建出一张 DAG

现在我们的问题就是，给定一张 DAG，上面某些点已经填好了标号，要求将 $1\sim n$ 中剩下的数填上去，使得最后标号形成合法的拓扑序（ $u\rightarrow v$ 则代表 $id_u>id_v$ ）

这个是可以解决的，我们对每个点求出一个限制条件 $[l_i,r_i]$，表示从已知的信息我们可以推出第 $i$ 个点的标号在 $[l_i,r_i]$ 内，而我们就是要把每个标号匹配一个限制条件，然后再额外满足未知点之间两两满足拓扑序关系

由于拓扑序靠前的点一定 $l$ 和 $r$ 的限制条件都更大，因此我们按 $r$ 从大到小扫描线，每次贪心选择 $l$ 最大的，多个 $l$ 相同的取下标最大的就是对的

复杂度 $O(2^nn)$

题解思路

结论：一个排名合法当且仅当 $\forall i,j,a_i\le a_{i\text{ OR }2^j}$

必要性：考虑归纳证明，设我们已知 $n^\prime<n$ 的所有 $n^\prime$ 对应的比赛都成立了，那么我们考虑说明 $n$ 阶比赛也满足性质

首先当 $j=0,1,\cdots,n-2$ 的时候可以通过更小的 $n$ 的结论推出一定成立，接下来考虑证明 $j=n-1$ 的部分：

考虑最后一轮比赛，我们做的实际上是把两个 $n-1$ 阶比赛的结果对位比较，然后第 $k$ 场比赛由两边排名为 $k$ 的人决出第 $2k$ 和 $2k+1$ 名

对于一个偶数 $i=2k$，那么最后排名为 $i$ 的人应该是第 $k$ 场比赛的胜者，而排名为 $i+2^{n-1}$ 的人应该是第 $k+2^{n-2}$ 场比赛的胜者

我们知道左边排名为 $k$ 的要比左边排名为 $k+2^{n-2}$ 的厉害，且右边排名为 $k$ 的要比右边排名为 $k+2^{n-2}$ 的厉害，那么 $i$ 应该就是这四个人中最厉害的，所以 $a_i\le a_{i+2^{n-1}}$

充分性是容易说明的，只要按蝴蝶变换构造即可

剩下的部分就和上面是类似的了

13. QOJ5573 - Holiday Regifting [K] ⭐

题面

给定一张 $n$ 个点 $m$ 条边的 DAG，保证 $1,2,\cdots,n$ 为一个合法的拓扑序，每个点有一个容量 $c_i$

点 $1$ 会不断接受礼物，每接受一个礼物后，礼物会以如下规则传递：

如果一个点发现自己的礼物个数达到了 $c_i$ 个，那么这个点会给每个出边指向的点恰好传递一个礼物，然后将自己的礼物数清零，保证每个点的 $c_i$ 大于等于出边个数

礼物在传递过程中点 $1$ 不会继续接受新的礼物

一开始所有点上都没有礼物，求点 $1$ 接受多少次礼物之后，礼物会再次全部消失，答案对 $998244353$ 取模

$1\le n\le10^4,0\le m\le3\times10^4,2\le c_i\le10^5$

题解

Sol

很酷。

直接计算每个点的周期不好算，考虑一种思路：我们逐次加入每个点，然后维护 $1\sim i$ 的整体周期

那么我们加入一个点的时候，如果我们能计算出来 $f_i$ 表示 $i$ 在一个 $1\sim i-1$ 的周期下会收到多少礼物，那么我们就知道需要给周期乘上 $\frac{f_i}{\gcd(f_i,c_i)}$

但是 $f_i$ 也很大，我们不好直接求出来，不过注意到我们只需要求出 $f_i\bmod c_i$ 的值即可知道每次需要乘多少

所以考虑一个分步计算的过程：

我们不断维护出 $1\sim i$ 周期下，后面的每个点会收到多少礼物，对 $c_i$ 取模
在求出一个新的 $i$，设 $x=\frac{f_i}{\gcd(f_i,c_i)}$，我们首先需要做的一件事情是将所有 $f_i$ 乘 $x$
然后按拓扑序依次遍历每个点，对所有出边贡献 $\lfloor\frac {f_i}{c_i}\rfloor$，然后令 $f_i\leftarrow f_i\bmod c_i$

相当于我们只要满了就贡献给后面的点，这样对 $\bmod c_i$ 的值是不影响的，但是可以控制我们的值域在 $c_i^2$ 以内

最后总复杂度即为 $O(n^2+nm)$

14. QOJ4217 - Graph Coloring [S]

题面

给定一个 $n$ 个点的竞赛图，将边染成不超过 $14$ 种颜色，使得不存在两条边 $i\rightarrow j$ 和 $j\rightarrow k$ 同色

$1\le n\le3000$

题解

Sol

使用 $\binom{14}7$ 为标号，任意两个不同标号 $i,j$ 一定有一位 $i$ 是 $0$，$j$ 是 $1$

15. ARC138C - Rotate and Play Game [S]

题面

给定长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$，一个人和一个波特在上面博弈，人先手：

每轮人可以任意选一个还没被取过的数把它取掉
每轮波特会选择下标最小的还没被去过的数把它去掉

人会在已知波特的策略下最大化选的自己取的数的和，这个即为人的得分

在所有操作前，你可以选择一个 $k$，将 $a$ 向左循环移位 $k$ 位，求一个使人得分最大的 $k$，以及这个最大的得分

$2\le n\le2\times10^5,1\le a_i\le10^9$，保证 $n$ 为偶数

题解

Sol

对于一个集合 $S$，人可以选择出这个集合 $S$ 的条件即为：我们创建一个新的数组 $c$，在 $S$ 中的数 $c$ 值都为 $-1$，否则为 $1$，那么 $c$ 的任意前缀和 $\ge-1$

取出 $a$ 中最大的 $\frac n2$ 个元素作为 $S$，求一个 $c$ 的前缀和数组，将 $c$ 中最小值循环移位到开头即可

16. QOJ10330 - Median Operations [E]

题面

给定一个 $1\sim n$ 的排列 $p$，保证 $n$ 为奇数

你会不断进行如下操作：选择 $p$ 一个长为奇数的子区间，将其中的元素删除，然后在这个位置插入一个这个子区间的中位数

最后会只剩下一个数，对每个 $k=1,2,\cdots,n$，求是否存在一种操作方式使得剩下的数是 $k$

$3\le n\le2\times10^5$

题解

Sol

显然可以变成只有 $-1,0,1$ 的问题。

结论：对于一个长为奇数的操作区间，我们可以将其拆成若干次长为 $3$ 的操作区间

结论：对于任意一个只包含 $-1,1$ 的串，经过若干次操作后，其能得到的和一定是一段区间内的所有奇偶性对的数

我们最后的目标就是要在不操作 $0$ 的情况下，让整个数列和为 $0$，因此我们只要支持单点修改，求出一个区间的最大和最小和即可

如果我们要最小化 $-1$ 的数量，那么一定是操作所有 $-1,-1,-1$，那么此时剩下可以改变和的就是 $-1,-1,1,-1,-1$ 一样的结构

处理这个我们可以使用一个栈（AGC022E - Median Replace）构建一个自动机来处理

注意到我们最后判断的是两个数加起来是否 $\ge0$，而一个数最小为 $-2$，所以我们 $1$ 的个数需要保留 $0/1/2/3/\ge4$ 个的状态

用线段树维护，最后的复杂度就是 $O(30n\log n)$

17. QOJ10322 - Matching Query [E]

题面

给定一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，以及一个常数 $m$，$q$ 次修改，每次修改一个单点的值，每次修改之后，输出如下问题的答案：

建一张 $n$ 个点的图，满足 $1\le u<v\le n$ 之间有边当且仅当 $a_u+1\equiv a_v\pmod m$，注意 $u,v$ 之间有顺序关系，求这张图的最大匹配

$2\le n\le3\times10^5,1\le q\le3\times10^5,2\le m\le3\times10^5$

题解

Sol

首先考察一次询问怎么做。

如果我们将 $i$ 和 $i+1$ 匹配，那么 $i$ 被使用的肯定是一段前缀，而 $i-1$ 和 $i$ 匹配使用的一定是一段后缀，这刚好不冲突

那么我们设 $x_i$ 表示有多少 $i$ 和 $i+1$ 匹配了，那么我们对这个 $x$ 的限制就是：$x_i+x_{i-1}\le cnt_i$，并且从左往右第 $j$ 个 $i$ 的位置比从左往右第 $cnt_{i+1}-x_i+j$ 个 $i+1$ 的位置更靠左，这个可以写成一个 $lim_i$ 的形式，即 $x_i\le lim_i$

问题就划分为了两部分：维护 $cnt_i,lim_i$，和计算这种情况下的最大 $\sum x_i$

第一部分，$cnt_i$ 是好维护的，考虑如何快速求 $lim_i$：如果我们将 $i$ 都看作 $1$，$i+1$ 都看作 $-1$，那么第 $j$ 个 $i$ 一定比第 $j+k$ 个 $i+1$ 靠左的条件即为所有前缀和都 $\ge-k$

那么开 $m$ 棵线段树维护一下即可，每次单点修改只会影响 $O(1)$ 个 $lim$ 和 $cnt$ 的值

第二部分，我们需要支持单点修改 $lim,cnt$，然后求整体的答案

可以认为这是一个经典问题。

注意到如果 $m$ 是偶数，那么这个东西是有网络流建模的，我们把奇数的限制从 $S$ 连出，偶数的限制连向 $T$，建一张图，最大流就是我们所求

如果 $m$ 是奇数，我们可以考虑把每个 $x$ 拆成两个变量 $y,z$，然后连限制 $y_i,z_i\le\frac12lim_i$，$y_i+z_{i+1}\le \frac12 cnt_i$，$z_i+y_{i+1}\le\frac12cnt_i$，这样就变成了一个 $2m$ 的问题

但是问题就是我们解出来的最优解可能不是整数，但是注意到如果我们最后的最优解有 $.5$ 状物，我们可以把一个 $.5$ 连续段调整成整数，唯一调整不了的情况是所有数都是 $.5$，这种情况我们的最优解就是此时的和 $-0.5$

也就是说我们把求出来的答案下取整即可

求最大流可以用线段树模拟最小割，存 $0/1,0/1$ 表示左右的点有没有被割即可

复杂度 $O(n\log n)$

18. QOJ10321 - Inversions of PQ and QP [E]

题面

给定 $n,A,B$，请构造两个 $1\sim n$ 的排列 $p,q$，使得：

$p_{q_1},p_{q_2},\cdots,p_{q_n}$ 的逆序对数为 $A$
$q_{p_1},q_{p_2},\cdots,q_{p_n}$ 的逆序对数为 $B$

给出构造或判断无解

$1\le n\le2\times10^5,0\le A,B\le\frac12n(n-1)$

题解

Sol

考虑构造出来两个排列 $x_i$ 和 $y_i$，然后再还原出 $p,q$

这两个排列需要满足什么性质才能还原 $p,q$ 呢，打表可以发现 $x$ 和 $y$ 的环长集合必须一样

事实上，这也是很符合直接的，考虑 $x$ 中的一个环，它一定是不断走 $q$ 边 $p$ 边走出的一个环，那么错一位之后，就应该对应着一个不断走 $p$ 边 $q$ 边走出的一个环，也就是 $y$ 中的一个环

这也为我们提供了一个构造方式：直接将 $x,y$ 中所有环找出来，按长度配对叠在一起，每个点的 $p$ 边和 $q$ 边都会被确定恰好一次

我们只要构造逆序对数满足条件的 $x,y$ 即可

注意到如果 $A,B$ 不同奇偶那么一定爆了。

而逆序对数最大值是由 $\lfloor\frac n2\rfloor$ 个大小为 $2$ 的环取到的，这种环长集合能造出的逆序对数最小为 $\lfloor\frac n2\rfloor$，再拼一下 $\lfloor\frac n2\rfloor+1$ 的（具体地，如果 $n$ 为偶数，我们可以直接用 $\frac n2-1$ 来造，否则我们需要使用 $(n-1)/2$ 个长为 $2$ 的环和一个长为 $3$ 的环），我们就已经能造 $\min(A,B)\ge\lfloor\frac n2\rfloor$ 的情况了

而我们不妨假设 $A$ 很小，那要在能造出逆序对数为 $A$ 的情况下让最大的逆序对数尽可能大，最大的就是对 $i\in[1,A]$ 交换 $i$ 和 $n+1-i$，这种就是最大的

不在这个范围内的都是无解的，这个和打表得到的结论是契合的

构造即可。

19. QOJ10323 - 2-Power Rush [K] ⭐

题面

定义 $f(n)$ 为：对于所有可重集 $S$，满足 $S$ 中的元素都为 $2$ 的次幂，且 $S$ 中元素和为 $n$，$S$ 中的元素乘积之和

给定 $T,a,b$，求 $\sum_{i=0}^{T-1}(f(n_i)\bmod 998244353)\oplus i$，其中 $n_i=(ai+b)\bmod2^{30}$

$1\le T\le10^7,0\le a,b<2^{30}$

题解

Sol

wonderhoy.

这个就是询问 $10^7$ 次求单点。

首先考虑如何求单点，注意到一件事情：对于一个 $n$，如果 $|S|\ge2$，令 $e$ 为使 $2^e<n$ 最大的 $e$，那么我们将 $S$ 升序排序之后一定存在一个前缀的和为 $n-2^e$

所以我们可以使用一个 dp，令 $f_{i,l,r}$ 表示我们当前 $n=2^i$，且能够使用 $2^l,2^{l+1},\cdots,2^r$，并且必须使用一个 $2^r$

然后再处理两个数组 $g_{S,i}$ 和 $h_{S,i}$，用高低位拆开

最后可以做到复杂度 $O(m^3+2^{m/2}m^2+Tm)$，其中 $m=30$

20. 集训队互测 2023 - 区间切割 [E]

题面

给定 $n$ 个区间 $[l_i,r_i]$，$m$ 次操作，每次操作给定一个正整数 $x_i$，和一个 $[1,n]$ 的子区间 $[L_i,R_i]$，表示将编号在 $[L_i,R_i]$ 内的区间从 $x_i$ 切割，即：

如果 $x\not\in[l_i,r_i]$，则不作任何改变
如果 $x\in[l_i,r_i]$，将 $[l_i,r_i]$ 变成 $[l_i,x_i]$ 和 $[x_i,r_i]$ 中较长的，如果长度相等则变成 $[l_i,x_i]$

求所有操作之后每个区间变成了什么

$1\le n\le10^5,1\le m\le10^6,1\le l_i\le r_i\le m$，保证 $x$ 为 $1\sim m$ 的排列

题解

Sol

小 trick 题。

注意到一件事情，一个区间 $[l,r]$，我们取出其中间的 $\frac13$ 的位置 $[pl,pr]$，如果 $xpr$，那么我们取的一定是包含 $[pl,pr]$ 的部分

有了这件事情之后，维护就变得容易了，我们只要对 $n$ 个区间扫描线，然后每次找到第一个切到 $[pl,pr]$ 的操作模拟即可

复杂度 $O(n\log^2n+m\log n)$

21. LOJ6703 - 小 Q 的序列 [K] ✨

题面

给定一个长为 $n$ 的序列 $c_1,c_2,\cdots,c_n$，求所有非空子序列 $a_1,a_2,\cdots,a_k$ 的 $\prod_{i=1}^k(a_i+i)$ 之和，对 $998244353$ 取模

$1\le n\le10^5$

题解

Sol

列出 dp 式：$f_{i,j}\leftarrow f_{i-1,j}+(a_i+j)f_{i-1,j-1}$

翻转一下系数，原来在 $j$ 的变到 $i-j$：$f_{i,j}\leftarrow f_{i-1,j-1}+(a_i+i-j)f_{i-1,j}$

对每个 $i$ 看成生成函数，那么就是 $F_i\leftarrow (a_i+i+x)F_{i-1}-xF^\prime_{i-1}$

这个还是不是很好看，有高人说，我们给前面乘上一个多项式 $H$，让所有转移都是齐次的

令 $G_i=HF_i$，则 $G_i^\prime=H^\prime F_i+HF_i^\prime$

而我们需要凑出一个 $-xHF_{i-1}^\prime$ 项，也就是说我们需要一个 $-xG_{i-1}^\prime$，而我们想要所有转移都是齐次的，所以我们只能造一个 $(a_i+i)G_{i-1}$，我们列出现在的转移式 $G_i=(a_i+i)G_{i-1}-xG^\prime_{i-1}$，如果 $xHF_{i-1}$ 和 $-xH^\prime F_{i-1}$ 一起消失掉了这就是非常好的

即我们的 $H$ 应满足 $H^\prime=-H$

如果你会一些手段，你可以得到 $H=e^{-x}$，但你不会的话也可以直接递推算出来

此时转移就是 $g_{i,j}\leftarrow (a_i+i-j)g_{i-1,j}$，那么我们只要对每个 $j$ 都求出 $\prod(a_i+i-j)$ 的值，乘上 $e^x$ 就能得到答案了

这个可以使用多项式多点求值解决。

复杂度 $O(n\log^2n)$

附件

多项式多点求值：

给定 $n$ 次多项式 $F(x)=\sum_{i=0}^nf_ix^i$，以及 $m$ 个数 $a_1,a_2,\cdots,a_m$，求 $F(a_1),F(a_2),\cdots,F(a_m)$

首先将 $n,m$ 补齐到同一个数，注意到我们这个是一个关于 $f$ 系数的线性变换，也就是说可以写成矩阵的形式，我们要求的即是：

$\begin{bmatrix}f_0&f_1&\cdots&f_{n-1}\end{bmatrix}\begin{bmatrix}1&1&1&\cdots&1\\a_0&a_1&a_2&\cdots&a_{n-1}\\a_0^2&a_1^2&a_2^2&\cdots&a_{n-1}^2\\\vdots&\vdots&\vdots&\ddots&\vdots\\a_0^{n-1}&a_1^{n-1}&a_2^{n-1}&\cdots&a_{n-1}^{n-1}\end{bmatrix}$

的各项系数

而这个我们不会做，可以转置一下：

$\begin{bmatrix}f_0&f_1&\cdots&f_{n-1}\end{bmatrix}\begin{bmatrix}1&a_0&a_0^2&\cdots&a_0^{n-1}\\1&a_1&a_1^2&\cdots&a_1^{n-1}\\1&a_2&a_2^2&\cdots&a_2^{n-1}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&a_{n-1}&a_{n-1}^2&\cdots&a_{n-1}^{n-1}\\\end{bmatrix}$

而这个就是对所有 $k$，求 $\sum_{i=0}^{n-1}f_ia_i^k$，而这个就是 $\sum\frac{f_i}{1-a_ix}$ 的每一项，可以分治维护分式维护，具体地，每层分治有如下的流程：

$P(l,r)=P(l,m)\times Q(m+1,r)+Q(l,m)\times P(m+1,r)\\Q(l,r)=Q(l,m)\times Q(m+1,r)$

边界情况是 $P(i,i)=f_i,Q(i,i)=1-a_ix$，最后的答案为 $P(1,n)\times Q(1,n)^{-1}$

现在我们要对这个过程转置。

将这个过程转置可以理解为从最后每个答案贡献到一开始的输入

$Q$ 和 $f$ 无关，所以我们可以一开始求出，转置完了之后即我们每个分治区间 $[l,r]$，穿进去一个多项式 $F$，然后令向 $[l,m]$ 中传入 $F\times^T Q(m+1,r)$，向 $[m+1,r]$ 中传入 $F\times^T Q(l,m)$

$\times^T$ 即为多项式乘法的转置，可以发现这就是差卷积

$F$ 可以只保留到区间长度，所以复杂度是 $O(n\log^2n)$ 的

22. UR26 - 铁轨回收 [E] ✔️

题面

给定两个长为 $n$ 的数列 $a_i,b_i$，按照 $i=1,2,\cdots,n-1$ 进行如下操作：

均匀随机选择一个 $j>i$，令 $a_i\leftarrow0,a_j\leftarrow\min(a_i+a_j,b_j)$

对 $k=0,1,2,\cdots,b_n$，求最后 $a_n=k$ 的概率，对 $998244353$ 取模

$1\le n\le50,0\le a_i\le b_i\le30$

题解

Sol

最后会形成一棵以 $n$ 为根的树，因此我们可以考虑倒着搜这棵树

搜到一个点 $i$ 时，我们决策这个点的父亲，以及最后这个父亲点上有多少值是从 $i$ 过来的

具体地，我们认为一个点溢出 $b$ 时，会把更靠前接受过来的值扔掉，那么我们倒着搜，枚举 $i$ 有多少值，就大概已经可以记状态了

我们设 $(i,S)$ 表示搜到 $i$ 及以后的点，并且当前要求一些点接受的值 $\ge x_i$，所有 $x_i$ 缩起来的状态是 $S$ 的

每次加一个新点 $i$，我们枚举 $i$ 的值 $\ge x_i$，设连到的父亲点权为 $\ge x_j$，那么我们直接要求其变为 $\ge x_i$ 和 $\ge\max(0,x_j-x_i)$

但是这样会算重，所以我们应用一下点减边容斥，再额外减去 $\ge x_i+1$ 和 $\ge\max(0,x_j-x_i)$ 的方案数

写出来发现跑的很快，但是因为哈希表常数太大过不了，状态数还是很少的，因此我们仔细分析一下能生成的状态数

相当于我们有一个可重集 $S$，一开始为 $0,1,2,\cdots,b_n$ 中的一个，接下来每次我们可以执行如下两种操作的一种：

选择一个 $v\in S$，将其分成 $x$ 和 $v-x$，满足 $0\le x\le v$
选择一个 $v\in S$，将其分成 $x+1$ 和 $v-x$，满足 $0\le x<v$

最后我们要求有哪些集合可以被得到。

我们给两种操作生成的元素都 $-1$，如果为 $0$ 就扔掉，那么二操作不会改变总和，一操作会让总和变小 $1$，那么就是大小 $\le n-i$，且和 $\le b_n$ 的非负整数可重集数量

令 $m=b_n$，这个就是 $O(nm^{0.5}\pi(m))$，转移再乘一个 $m$，再乘一个 $n$ 表示考虑了多少，总复杂度是 $O(n^2m^{1.5}\pi(m))$

这样我们就可以预处理出来所有 $\le m$ 的划分数加或者删去一个点之后会到哪个划分，可以小常数

23. AGC017F - Zigzag [E] ⭐

题面

一个边长为 $n$ 的正三角形点阵，第 $i$ 行有 $i$ 个点，你需要选 $m$ 条折线，从 $(1,1)$ 出发，每步从 $(i,j)$ 走到 $(i+1,j)$ 或 $(i+1,j+1)$

你需要满足如下条件：

对第 $i,j(i<j)$ 条折线，第 $i$ 条折线必须一直非严格在第 $j$ 条折线左边
额外给定 $k$ 条限制，形如第 $a$ 条折线的第 $b$ 步必须走到 $(i+1,j)/(i+1,j+1)$

求满足条件的折线数量，对 $10^9+7$ 取模

$1\le n\le20,1\le m\le20$

题解

Sol

直接 dp 需要记的东西有点多，比如我们需要记 $i,j,k,S$，表示当前是第 $i$ 条折线，现在确定了 $j$ 行及以上的决策，且上一条折线 $j$ 行经过的第二维坐标是 $k$，$S$ 表示当前两条折线的状态拼起来

这样是 $O(n^32^n)$ 的，并且也很丑。

这个做法的主要问题在于我们需要同时记录两条折线的状态，能不能只记录一条呢？

那么一个想法就是一点点调整这个 $i-1$ 的折线，把它变成 $i$ 的折线

具体地，我们按照如下过程调整：

初始化折线 $X$ 为 $i-1$ 的折线，扫描 $j=1,2,\cdots,n-1$，如果第 $j$ 步 $i$ 和 $X$ 不一样，那么一定是 $X$ 这一步向左，$i$ 这一步向右，那么我们将 $X$ 调整为这一步向右走，然后一直向左走直到和原来的 $X$ 相撞为止，然后继续进行下一个 $j$ 的过程

容易发现这样确定的过程是唯一的，那么我们就可以对这个列 dp，令 $dp_{i,j,S}$ 表示我们当前考虑第 $i$ 条折线，确定了前 $j$ 位，当前状态为 $S$，转移是 $O(1)$ 的，容易用滚动数组将空间优化到 $O(2^n)$

总复杂度 $O(n^22^n)$

24. AGC018F - Two Trees [E] ⭐

题面

给定两棵 $n$ 个点的有根树 $T_1,T_2$，要求构造整数序列 $x_1,x_2,\cdots,x_n$，使得如下条件成立：

对于任意一棵树 $T\in\{T_1,T_2\}$，任意一个节点 $u\in[1,n]$，都有 $u$ 的子树 $x$ 值和的绝对值为 $1$

给出构造或判定无解

$1\le n\le10^5$

题解

Sol

令 $s_{1/2,u}$ 表示 $u$ 在 $T_{1/2}$ 中的子树和，那么所有 $s$ 变量的应为 $\pm1$

问题可以转化为构造一组 $s_{1/2,u}$ 变量，使得其对所有 $u$ 满足：$s_{1,u}-\sum_{v\in ch_{1,u}} s_{1,v}=s_{2,u}-\sum_{v\in ch_{2,u}}s_{2,v}$

这个看起来有点感觉了，如果我们把 $s$ 变量看成给 $u$ 到父亲的边定向，那么我们两边的东西就都变成 $u$ 的入度减出度了，这个就极大概率是欧拉回路了。

但是这个相等的限制我们还是不好做，所以我们做一步操作：将第二棵树上所有值取反

那么现在就是两个点的入度减出度加起来是 $0$，我们直接把这两个点叠起来跑欧拉回路即可，没有说明无解。

可以额外发现无解的情况就是 $u$ 在两棵树中儿子个数奇偶性不同，这个确实是无解的，进一步验证了我们是对的。

复杂度 $O(n)$

25. AGC019F - Yes or No [E]

题面

有 $n+m$ 个判断题，$n$ 个答案为 Yes，$m$ 个答案为 No

你会以均完全随机的顺序收到这些判断题，你现在要猜出来尽可能多的答案，你回答完一道题之后会立刻知道这道题的答案，你会遵循期望答对题数尽可能多的策略，求期望答对的次数，对 $998244353$ 取模

$1\le n,m\le5\times10^5$

题解

Flamire 做法

Sol

不妨假设 $n>m$，可以发现这个题的答案是什么和你猜的是什么无关，所以你一定会去猜数量更多的那个

可以发现我们求的就是从 $(0,0)$ 走到 $(n,m)$ 经过下图中红线的数量：

但是直接 dp 是不好优化的。

考虑以经过 $y=x$ 直线的部分给折线分段，枚举两次相邻的经过 $j,i(j<i)$，那么贡献式应该如下：

$\sum_{0\le j<i\le m}\binom{2j}{j}C_{i-j-1}(i-j+i-j+1)\binom{n-i+m-i}{n-i}$

其中 $C$ 为卡特兰数

这个式子可以用卷积优化到 $O(n\log n)$

最后一次经过之后的式子是可以类似列的，但是只用枚举一个值，所以是 $O(n)$ 的

总复杂度 $O(n\log n)$

题解做法

Sol

任意一个折线经过红线的数量就是 $n$ 加上在 $y=x$ 直线向上的步数

那么就可以 $O(n)$ 算了。