~~换个地方被吊打~~

Day1

今天主要是考试和讲题，但是今天我生病了头痛欲裂，所以没有写什么题，主要是休息吧。晚上吃了一些药，情况稍有改善后改了两道题。

Day2

今天上午是自己写题，下午讲解了数据结构。学习的新知识是：

ZKW线段树
圆方树和点双tarjan

对于一些数据结构的trick有了新的理解。

A - Ice-cream Tycoon

题意：要求维护一个冰激凌集合，支持如下两种操作：

加入 $n$ 个价值为 $c$ 的冰激凌
出售最便宜的 $n$ 个冰激凌。如果这些钱大于 $v$ ，不操作，并且报告 $Unhappy$ ；反之删去这些冰激凌，返回 $Happy$ 。

思路点拨：本题比较简单

考虑对于全部的询问离线下来后离散化，使用线段树上二分判断是否买得起。十分基础，时间复杂度 $O(n \log n)$ 。

B - New Year Tree

给定一棵树，每一个节点有一个颜色。你需要编写一种数据结构，支持如下两种操作：

将子树全部的颜色改为 $c$ 。
询问字数内的颜色有多少种。

数据保证所有颜色的数量不超过 $60$ 种。

思路点拨：本题比较简单

考虑通过 dfs序将树上问题转化为序列上问题。
我们使用一个线段树维护区间上的颜色。对于一个区间的颜色表示，我们使用一个二进制压缩的数表示即可。pushup函数就两个儿子的颜色并。
子树颜色赋值就是区间赋值操作，维护一个懒标记。

时间复杂度 $O(n \log n)$ 。

C - Ping-Pong

你需要维护一个区间集合，支持如下两种操作：

添加一个区间[l,r] ，保证这个区间的长度严格大于之前的全部区间
查询第 $i$ 个区间是否可以直接或间接到达第 $j$ 个区间。我们认为两个区间 $[l1,r1]$ 和 $[l2,r2]$ 可以到达,就是 $l2<l1<r2$ 或者 $l2<r1<r2$ 。注意，这种到达是一种单向到达的关系。

思路点拨：本题十分困难

我们考虑对于第 $i$ 个区间，我们要到达区间 $j$ ，我们可以不断地往右走或者往左走，找到这个极大区间 $[l,r]$ 。我们对于区间 $j$ ，按照同样的方法找到极大区间 $[x,y]$ 。如果这两个区间满足 $[l,r]$ 到 [x,y] 有单向到达关系或者 $[l,r]$ 和 $[x,y]$ 本质是一样的，可以证明区间 $i$ 和区间 $j$ 可达。这个证明比较繁琐，但是画画图是可以推出来的。没有这个结论做不了这题，这也是本题的难点。
我们考虑维护一种数据结构，通过并查集的方式让每一个区间指向它可以到达的极大区间。我们维护这些极大区间。那么每一次加入一个区间的时候，我们可以将跟这个区间有交的极大区间给合并起来，形成一个新的极大区间。问题是，我们怎么找到有交的区间呢？
我们考虑对于每一个线段树的节点维护一个set，那么每一次添加一个区间，我们就将在线段树上被这个区间完全包含的 $\log n$ 个区间（这是指线段树上的区间，下同）的集合种添加一个标记。每一次合并的时候，我们又找到与这个区间有交集的 $\log n$ 个区间，将标记区间所在的极大区间合并起来。最后删去这个无用标记。
我们考虑计算时间复杂度，每一次我们打上 $O(\log n)$ 个标记。这些标记会被标记一次，又被删除一次，所以时间复杂度是 $O(n \log n)$ 的。

D - Life as a Monster

题意：平面上有 $n$ 个点，你需要编写一个程序支持如下两种操作：

更改一个点的坐标
查询某一个点到其余点的切比雪夫距离之和

强制在线，空间比较紧张。

思路点拨：本题难度适中

切比雪夫距离转曼哈顿距离。
我们考虑一个点距离其余点的曼哈顿距离可以转化为 $\sum |x-x_i| + |y-y_i|$ 。我们发现横纵坐标是相对独立的，所以我们分别考虑。剩下的部分使用一个动态开点权值线段树维护坐标和即可。

主要是切比雪夫距离转曼哈顿距离的trick需要知道。

E - Tourists

题意：给定了一个无向图，点有点权。你需要编写一个程序支持如下两种操作：

更改一个点的点权
查询在 $u,v$ 的路径上，在不经过相同点的情况下可以到达的最小点权。

思路点拨：本题难度适中

考虑一个联通块什么时候可以在不经过重复点的情况下到达任意点，这是一个点双。
我们考虑建立一个圆方树，方点维护这个点双的最小点权。但是每一次更改可能牵扯到多个方点，所以我们钦定一个根，并且让一个方点只管辖它的儿子节点的最小权值，这样的时间是正确的。
每一次查询，我们在圆方树上树剖求链上最小值，如果LCA是一个方点，答案就考虑这个方点的父亲节点的点权。

F - New Year and Conference

题意：现在有两个会场，每一个演出会在$[l1,r1]$ 在会场1演出，$[l2,r2]$ 在会场二演出。问是否存在一个子集 $S$ ，是的这个自己中的演出在第一个会场没有交集，在第二个会场中存在时间重合。

思路点拨：本题比较简单。

其实 S 的大小我们只要考虑 $|S|=2$ 。这个结论是很容易知道的。
我们考虑枚举重叠的区间的时间靠后的一个区间，双指针扫出哪些与这个区间的另一会场没有时间交集的那些区间，接下来考虑在这些区间中是否存在区间与本区间有交集。这样我们维护一个线段树判断是否有交集就可以了。

Day3

A Roadside Trees(*3000)

题目描述

路边有 $n$ 个位置，每一个位置可能生长着一棵树。每棵树每个月生长了一个高度，每一个月的开始，会进行如下操作之一：
在 $p$ 位置种植一颗高度为 $h$ 的树。
砍掉从左往右第 $c$ 颗树，这个位置不能再种树。
$h,c \leqslant 10$ 。

保证任意时刻不存在两颗高度相同的树。

每一次操作后查询最长上升子序列。

思路点拨

我们发现树会长高，十分烦躁。当我们种下一棵树的时候，我们将树的初始高度减去目前的时间 $T$ 。这样就转换成了静态问题，不需要考虑树生长的结果。

我们考虑到一半的最长上升子序列的转移柿子，对于一个元素 $c$ ，我们如果需要去除这个元素，只会对下标小于 $c$ 的元素造成影响，所以我们可以轻松解决第二个操作。

又因为树的高度两两不同，所以对于插入的一颗高度小于等于 $10$ 的树，至多对 $10$ 颗树造成影响。

时间复杂度 $O(10n\log^2 n)$ ，可以通过。

B Noble Knight's Path（*3000）

给一棵树，现在有两种询问：
标记某个节点
找到路径 $a->b$ 再第 $k$ 次询问到当前询问之间没有被标记的第 $k$ 个节点。

思路点拨

对于在 $k$ 次操作之后的关于标记的维护，考虑主席树，这样十分方便。加上树上询问，套树剖。

特别的，在路径的 $LCA$ 处需要特别处理。
时间复杂度 $O(n \log ^2 n)$ 。

C 区间本质不同子串个数

$\text{SAM}$ 的题，太逆天。

D Cyclic Distance

太逆天，待补。

E HUD 7144 Treasure

给定一张边带权的无向图，每个点有一个颜色和一个权值。保证对于一种颜色，拥有这个颜色的点数不超过 10。现在要求支持以下两种操作
增加一个点的权值。
询问从一个点出发，不经过边权超过 x 的边，其所有可能到达的点中，每个颜色的最大权值之和。

思路点拨

对于边权限定这一块，考虑使用 $\text{Kruskal}$ 重构树转换成子树问题。

那么对于一个节点，我们需要增加权值的话，我们只需要找到从它开始，可以在哪一段路径上成为最大值。这个可以路径修改操作，使用树剖。查询自然不在话下。

时间复杂度 $O(10n\log^2n)$ 。

考虑到颜色的数量十分的稀少，所以完全可以建虚树，时间复杂度 $O(10n\log n)$ 。

G-JOI 稻草人/手办

题目描述

二维平面上有 $n$ 个节点，问有多少点对 $i,j$ 满足：

$x_i <x_j,y_i<y_j$
不存在 $x_i < x_k <x_j ,y_i<y_k<y_j$ 。
$n \leqslant 2\times 10^5$ 。

思路点拨

离散化后即为给定一个排列，要求找出 $i<j$ 满足 $p_i<p_j$，不存在 $i<k<j$ 满足 $p_i<p_k<p_j$。
复杂二元组计数考虑进行分治，固定左侧 $i$ 考察右侧有多少 $j$ 满足要求。
$i$ 在左部的后缀中最小的大于 $p_i$ 的元素给出 $j$ 最大值的限制，另外 $ j$ 在右部的前缀中不能有 $p_i<p_k<p_j$ 的 $p_k$。
不妨按照大小顺序，从大到小加入 $p_i$。同时维护所有满足条件 $>p_i$ 的 $p_j$。加入一个 $j$ 时，$p_j$ 右侧的所有 $j’$ 显然满足 $p_i<p_j<p_j’$，需要删除。这样可能的 $j$ 形成 $p_j$ 单调下降的序列，可以二分求出最后一个满足条件的 $j$。
通过单调栈维护可能的 $j$ ， $\text{BIT}$ 记录前缀和
复杂度 $O(n \log n \log n)$ 。

test0717

今天的模拟赛太逆天了。 $\text{NOIP}$ 模拟赛一紫三黑。
只会 $T1$ ，无语

T1 珠宝

题目描述

有 $n$ 个物品，每一个物品有一个空间 $w_i$ 和一个价值 $v_i$ 。

你有一个空间为 $i$ 的背包，问最多可以装下多少价值的物品。

问价值 $i \leqslant K$ 时的每一个答案。

数据范围 ： $n \leqslant 1e6$ , $K \leqslant 5e4 $ , $w \leqslant 300$ 。

思路点拨

我们按照一般的 $\text{01}$ 背包的思路，本题可以做到 $O(nk)$ ，严重超时。

我们比较一般的背包问题的数据规模和本题的数据规模，本题的物品数量十分庞大，但是物品的空间很小。

我们从物品的空间下手，从 $1$ 到 $300$ 枚举一个空间 $V$ 。对于每一个空间时 $V$ 的物品打包考虑。

首先，我们可以将这些物品价值降序排序，因为我们在同样的空间下总是会先选价值大的。

接下来，我们对这些物品做前缀和，保存到数组 $g_{i \times V}$ 中，表示选择 $i$ 个空间为 $V$ 的物品的价值。

转移的时候，我们发现，两个状态 $f_{i}$ 和 $f_{j}$ 会互相影响仅当 $i \mod V = j \mod V$ 。

所以我们枚举我们要转移的状态 $\mod V$ 的余数，假设他为 $z$ 。

那么我们将形如 $f_{i \times V+z}$ 的状态放在一起考虑，得到转移方程：

\[f_{i \times V+z} = \max \{ f_{i \times V+z} , \max \{ f_{j\times V+z} + g_{(i-j)\times V}\} \} \]

这个式子对我们的时间没有任何的优化，但是 $g$ 函数的增长率时单调不递增的。证明略。

所以我们的决策点有单调性，使用分治或者单调队列上二分均可通过。本题还算是比较可做的。

T2 [JOI 2020 Final] 火事

题目描述

给定一个长为 $N$ 的序列 $S_i$，刚开始为时刻 $0$。

定义 $t$ 时刻第 $i$ 个数为 $S_i(t)$，那么：

\[\left\{ \begin{array}{ll} S_0(t)=0\\S_i(0)=S_i\\S_i(t)=\max\{S_{i-1}(t-1),S_i(t-1)\} \end{array} \right.\]

你将对 $Q$ 个操作进行评估，第 $j$ 个操作让时刻 $T_j$ 时的区间 $[L_j,R_j]$ 全部变为 $0$。

执行一个操作需要一定的代价，执行第 $j$ 个操作需要以下的代价：

\[\sum\limits_{k=L_j}^{R_j}S_k(T_j) \]

求每个操作需要的代价。

注意：每个操作都是独立的。

思路点拨

考虑 $S_{i}(t)=\max_{j=i-t}^{i}\{a_i\}$ ，所以我们可以获得 $O(n^2)$ 的暴力。

但是，当我们把 $S_i(t)$ 画出来之后，我们发现对于每一个数的贡献十分的有规律，呈现出一个平行四边形。例如：

对于一个节点，我们定义 $L_i$ 为左边第一个大于它的数的下标， $R_i$ 为右边第一个 大于等于 它的数的下标。

这个平行四边形的顶点分别是 $(i,0),(i,i-L_i-1),(R_i-1,R_i-i-1),(R_i-1,R_i-L_i-2)$ 。

那么每一次询问就是问一个线段 $[l,r]$ 在纵坐标为 $t$ 的时候所经过的点的权值和。这个显然是可以差分简化问题的。

我们可以考虑将一个个平行四边形拆成若干个有规律的部分，使得可以更加方便计算。

一种十分简单的想法就是把一个平行四边形按照横坐标拆成一个个竖线，这样很好处理，但是全部的竖线数量过多。

我们注意到，如果按照纵坐标可以划分成一条条斜线。按照横坐标可以划分成 $R_i-i$ 个竖线，按照纵坐标可以划分成 $i-L_i$ 条斜线。

如何保证线的数量有限，可以利用笛卡尔树一个广为人知的结论 $\sum_{i} \min\{i-L_i,R_i-i\}$ 是 $O(n \log n)$ 级别的。给出一个证明：

这个式子相当于询问笛卡尔树的每一个节点的左右儿子子树的最小值之和。

我们可以把 $\min$ 换一种理解方式，把 $i$ 有左右两个儿子变换成将 $i$ 的两个儿子合并。这样取 $\min$ 就可以变换成启发式合并。

每一个节点至多被合并 $\log n$ 次，所以总体是 $O(n \log n)$ 的。

接下来，我们对于横线和斜线分别考虑。

横线十分简单，将全部询问差分后离线下来就可以扫描线，比较无脑。

斜线不好搞，对于一群在同一条斜线上的点 $(x,y)$ ，我们发现随着 $x$ 加上一个 $1$ ， $y$ 也会加上一个 $1$ 。也就是说，同一条斜线上的点 $x-y$ 是一个定值。

我们将原平面直角坐标系的点 $(x,y)$ 变换成 $(x-y,y)$ 就可以将斜线转换成横线。因为在同一斜线上的点 $x-y$ 是定值。

对于斜线转换后的横线，我们可以如法炮制同样操作。在维护扫描线的时候，考虑到本题时限比较紧张，使用 $\text{BIT}$ 维护。

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

T3 Mousetrap

题目描述

有一个有 $n$ 个房间和 $n-1$ 条走廊的迷宫，保证任意两个房间可以通过走廊互相到达，换句话说，这个迷宫的结构是一棵树。

一个老鼠被放进了迷宫，迷宫的管理者决定和老鼠做个游戏。

一开始，有一个房间被放置了陷阱，老鼠出现在另一个房间。老鼠可以通过走廊到达别的房间，但是会弄脏它经过的走廊。老鼠不愿意通过脏的走廊。

每个时刻，管理者可以进行一次操作：堵住一条走廊使得老鼠不能通过，或者擦干净一条走廊使得老鼠可以通过。然后老鼠会通过一条干净的并且没被堵住的走廊到达另一个房间。只有在没有这样的走廊的情况下，老鼠才不会动。一开始所有走廊都是干净的。管理者不能疏通已经被堵住的走廊。

现在管理者希望通过尽量少的操作将老鼠赶到有陷阱的房间，而老鼠则希望管理者的操作数尽量多。请计算双方都采取最优策略的情况下管理者需要的操作数量。

注意：管理者可以选择在一些时刻不操作。

对于所有的数据，$1 \le n \le 10^6$。

思路点拨

题目意思比较复杂，所以使用了更为清晰的原题面。

我们为了简化问题，我们将陷阱房作为数的根，这样老鼠就尽量远离根。

我们考虑这只倒霉的老鼠会怎么走。它会一头栽进一个子树然后被自己弄脏的路径困住。

那么在此时，我们伟大的管理员就可以把所有要封死的路径给堵住，最后把老鼠的路径擦干净。

我们先看看在一颗子树中，管理员的操作吧。我们定义 $f_i$ 表述老鼠从 $i$ 子树，和管理员斗智斗勇之后被堵在叶子然后回到 $i$ 管理员的最小步数。

我们考虑类似于数学归纳法的方式求出这个 $f_i$ 。也就是，在求 $f_i$ 的时候，我们知道 $i$ 的全部儿子的 $f_i$ 。

那么如果管理员无动于衷，老鼠会干什么？肯定会选一个 $f_i$ 最大的儿子的子树钻进去，以此拖延时间。

管理员此时是有一个步骤的，所以他可以把这个最大的 $f_i$ 堵住，老鼠就会走第二大的。有：

\[f_{i} = \text{2nd_max} \{f_{son}\}+\text{child} \]

$\text{child}$ 是儿子的个数。为什么是加上 $\text{child}$ 呢？

这是因为，我们的老鼠会钻进一个第二大 $f_{i}$ 的子树，那么其他 $\text{child-1}$ 个子树的边我们肯定是要堵上的，最后还要帮老师擦干净一条边。

为什么子树内的边要堵上，有没有可能不堵边更优秀呢？不可能，因为老鼠钻进这条边就至少要擦一条边让他出来。不如花一条边堵上，多一事不如少一事。

对于 $f_i$ 而言，老鼠钻进了子树后被堵在的一个叶子，我们此时需要把 $fa_i$ 到陷阱房之间不要的岔路堵上，这个我们记录为 $g_{fa_i}$ 。

$g_{i} $怎么求呢？我们考虑从父亲继承。先放出方程：

\[g_{i}=g_{fa_i}+\text{child}-[i\neq st] \]

其中 $st$ 是起点。如果 $i$ 不是起点，那么我从起点到达 $i$ 的时候就会弄脏一条边，我们只需要擦掉 $\text{child}-1$ 条别的边就可以了。

但是，老鼠一开始不一定会往自己的子树钻，有可能会走到别个子树钻进去。这是十分复杂的。

注意到答案可以二分，我们对于一个值 $\mid$ ，判断是否可以处理。我们模拟老鼠的每一个决策，给出代码（有注释）：

bool lis[MAXN];//在s到t的路径上 
bool check(int step){
	int sum=0;//管理先手
	for(int x=s;x!=t;x=dad[x]){
		sum++;//我多一步
		int ned=0;//这是我需要的步数
		for(int i=0;i<e[x].size();i++){
			int to=e[x][i];
			if(lis[to]) continue;
			if(f[to]+g[x]<=step) continue;
			if(!sum) return 0;//步数不够，管理员速度不行
			sum--;//少了一步 
			ned++;//这是要堵上的 
		}
		step-=ned;
		if(step<0) return 0;
	} 
	return 1;
}

总体时间复杂度 $O(n \log V)$ 。

这题太逆天了！

T4 小丑

题目描述

给定一张 $n$ 个点， $m$ 条边的无向图。有 $q$ 次询问，每次询问给出一个区间 $[l,r]$ 问在删去这个区间的边后图是否是二分图。

思路点拨

我们发现删除操作十分的恶心，考虑转换成添加操作。我们可以将边的数组开两倍，对于一次删除操作 $[l,r]$ :

我们可以转换成判断 $[r+1,l'-1]$ 是不是二分图。可以想到，对于每一个 $r$ ，我们找到一个最小的 $pos_r$ 使得 $[r+1,pos_r]$ 不是二分图。

怎么求解 $pos$ ?我们先考虑单个 $l$ ，这个 $pos_l$ 显然是可以二分的。我们二分一个 $pos_r$ 使用染色法或者并查集判断是不是二分图。时间复杂度 $O(nq\log n)$ 。

其实，$pos $ 数组具有单调性，所以我们可以使用分治法优化这个二分的过程。

发现在分治的过程中，对于每一个分治的段，我们都需要花费大量时间计算并查集。但是，这个并查集可以从分治树的父亲处继承一部分。维护可持久化并查集或者可撤销并查集即可。

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

test0719

本场比赛难度还可以，T1和T2还是比较可做。但是题目编排三道计数我真服了。

T1 镜子

思路点拨

首先，对于一般的情况可以拆点分开考虑方向，比较简单。这不是本题的重点。

你可能会疑惑，一面添加的镜子可以用两面，这一点该如何处理？

如果一个格子放了两个镜子，又该怎么办？

其实，上述疑惑都是没有必要的。看图：

至于一个格子放两个镜子的情况，大家可以感性一下，如果这个格子被经过两个不同的方向，还是由不同方向的镜子折射的，这一定是不优秀的。我们根本不需要考虑上述两种情况。

本题时限比较紧张，考虑到边权只有 $0,1$ ，所以 $\text{01bfs}$ 即可。

T2 [USACO20DEC] Sleeping Cows P

题目描述

Farmer John 有 $N$（$1≤N≤3000$）头各种大小的奶牛。他原本为每头奶牛量身定制了牛棚，但现在某些奶牛长大了，使得原先的牛棚大小不够用。具体地说，FJ 原来建造了 $N$ 个牛棚的大小为 $t_1,t_2,…,t_N$，现在奶牛的大小为 $s_1,s_2,…,s_N$（$1≤s_i,t_i≤10^9$）。

每天晚上，奶牛们都会按照某种方式寻找睡觉的牛棚。奶牛 $i$ 可以睡在牛棚 $j$ 中当且仅当她的大小可以进入牛棚（$s_i≤t_j$）。每个牛棚中至多可以睡一头奶牛。

我们称奶牛与牛棚的一个匹配是极大的，当且仅当每头奶牛可以进入分配给她的牛棚，且对于每头未被分配牛棚的奶牛无法进入任何未分配的空牛棚。

计算极大的匹配的数量模 $10^9+7$ 的结果。

思路点拨

我们先可以发现一些显然的事实：

本题的组合意义并不是十分明显，计数题可以考虑动态规划。
我们没有考虑给其分配牛棚的体积最小的牛也必须大于最大的未匹配牛棚，不然会不合法。

为了消除第二点事实给我们带来的繁杂的影响，我们考虑将牛和牛棚放一起排序。这个 $\text{trick}$ 十分优美。

现在我们想想我们的状态需要一些什么。

目前考虑到的下标，这是显然的。

目前待选择牛棚的牛的数量，因为牛棚会减少牛的数量，选择牛会增加牛的数量。

还有一点，我们讲到第二点事实所引出的，需要记录目前下标内的牛是否被全选。

综合下来，我们定义 $f_{i,j,k}$ 表示考虑到下标为 $i$ 的牛或者牛棚， $j$ 头牛需要牛棚， $k$ 是特殊状态。$0$ 表示前边可以选择的牛都找到牛棚了或者待找到牛棚， $1$ 反之。

考虑转移分两类讨论——牛和牛棚：

牛的转移

目前这头牛我们可以选或者不选，对于之前就有没选择的牛的那些状态：

\[f_{i+1,j,1}+=f_{i,j,1},f_{i+1,j+1,1}+=f_{i,j,1} \]

之前的牛都选择的那些状态的转移：

\[f_{i+1,j+1,0}+=f_{i,j,0},f_{i+1,j,1}+=f_{i,j,0} \]

为什么是 $f_{i+1,j,1}+=f_{i,j,0}$ ?因为我们如果不选牛的话状态 $k$ 这一维状态就改变了。

牛棚的转移

目前我们存在牛未选的话，这个牛棚必须选，比较简单，略。

如果全部的牛都选的话，这个牛棚爱选不选都可以：

\[f_{i+1,j-1,0}+=f_{i,j,0}\times j,f_{i+1,j,0}+=f_{i,j,0} \]

上述的转移都是比较好理解的吧。

我们的初始状态就是 $f_{0,0,0}=1$ ,$f_{2\times n,0,0}+f_{2\times n,0,1}$ 就是答案。

时间复杂度 $O(n^2)$ ，可以通过。

T3 [JOISC2018] 修行

题目描述

求有多少个长度为 $n$ 的排列恰好有 $k$ 个位置满足 $a_{i}>a_{i+1}$ 。

对于 $49 \%$ 的数据， $n \leqslant 3\times 10^3$ ;
对于 $100 \%$ 的数据，$n \leqslant 10^5$ 。

思路点拨

部分分

本题的 $O(n^2)$ 暴力是显然的。考虑动态规划，因为直接做有后效性，所以改成插入制。

定义 $f_{i,j}$ 表示已经考虑了 $1$ 到 $i$ ，有 $j$ 个位置满足前面比后面大。

转移分两类讨论，$j$ 是增加还是不增加。有 $f_{i,j}=f_{i-1,j}\times j+f_{i-1,j-1}\times (i-j+1)$ ，比较好理解，这里不细细讲解。

正解

考虑容斥，令 $f_{i}$ 表示恰好有 $i$ 个位置满足前面比后面大， $g_{i}$ 表示至少有 $i$ 个位置满足前面比后面大，有：

\[g_{i}=\sum_{i \leqslant j} C_{j}^i f_{j} \]

二项式反演得：

\[f_{i} = \sum_{i \leqslant j} (-1)^{j-i}C_{j}^i g_{j} \]

那么我们考虑 $g_{i}$ 的一般做法。其实就是盒子与球问题吧，球和盒子都是不同的，具体算的话参考囧仙的博客

\[g_{k}=\sum_{i=0}^{n-k} (-1)^{n-k-i}C_{n-k}^i i^n \]

我们带回一般式：

\[f_{k}=\sum_{k \leqslant i} (-1)^{i-k}C_{k}^ig_{i} \]

\[=\sum_{k \leqslant i} (-1)^{i-k}C_{k}^i\sum_{j=0}^{n-i}(-1)^{n-i-j}C_{n-i}^j j^n \]

有两个 $(-1)^x$ 形式的式子十分烦躁，所以我们考虑转换枚举顺序：

\[=\sum_{i=0}^{n-k}(-1)^{n-k-i}i^n\sum_{k \leqslant j \leqslant n-j} C_{n-j}^i C_{j}^k \]

前边都是快速幂的柿子，我们想后边的卷积： $\sum_{k \leqslant j \leqslant n-j} C_{n-j}^i C_{j}^k$

其实它是有组合意义的，就是我们考虑将 $n+1$ 个数划分成 $i+k+1$ 三个部分。我们考虑枚举其中的那个断点 $j$ ,那么左边可以选择 $C_{j}^{k}$ ，右边可以选择 $C_{n+1-(j+1)}^{i}=C_{n-j}^{i}$ 。

所以上述的卷积柿子就是 $C_{n+1}^{i+k+1}$ 。带回原柿：

\[f_{k}=\sum_{i=0}^{n-k}(-1)^{n-k-i}i^n C_{n+1}^{i+k+1} \]

JZTXT

成都集训游记

Day1

Day2

Day3

题目描述

思路点拨

思路点拨

思路点拨

题目描述

思路点拨

test0717

T1 珠宝

题目描述

思路点拨

T2 [JOI 2020 Final] 火事

题目描述

思路点拨

T3 Mousetrap

题目描述

思路点拨

T4 小丑

题目描述

思路点拨

test0719

T1 镜子

思路点拨

T2 [USACO20DEC] Sleeping Cows P

题目描述

思路点拨

牛的转移

牛棚的转移

T3 [JOISC2018] 修行

题目描述

思路点拨

部分分

正解