自己整理的板子。背背背！

以后如果打ACM的话复建说不定能用到（雾

AFO啦。

大概是退役前学的最后一个算法了吧写个学习笔记纪念一下。

应用的后台一共有 $N$ 个女性和 $N$ 个男性，他们每个人都希望能够找到自己的合适伴侣。为了方便，每个男性都被编上了 $1$ 到 $N$ 之间的一个号码，并且任意两个人的号码不一样。每个女性也被如此编号。

JYY 应用的最大特点是赋予女性较高的选择权，让每个女性指定自己的“如意郎君列表”。每个女性的如意郎君列表都是所有男性的一个子集，并且可能为空。如果列表非空，她们会在其中选择一个男性作为自己最终接受的对象。

JYY 用如下算法来为每个女性速配最终接受的男性：将“如意郎君列表”中的男性按照编号从小到大的顺序呈现给她。对于每次呈现，她将独立地以 $P$ 的概率接受这个男性（换言之，会以 $1-P$ 的概率拒绝这个男性）。如果她选择了拒绝，App 就会呈现列表中下一个男性，以此类推。如果列表中所有的男性都已经呈现，那么中介所会重新按照列表的顺序来呈现这些男性，直到她接受了某个男性为止。显然，在这种规则下，每个女性只能选择接受一个男性，而一个男性可能被多个女性所接受。当然，也可能有部分男性不被任何一个女性接受。

这样，每个女性就有了自己接受的男性（“如意郎君列表”为空的除外）。现在考虑任意两个不同的、如意郎君列表非空的女性 $a$ 和 $b$，如果 $a$ 的编号比 $b$ 的编号小，而 $a$ 选择的男性的编号比 $b$ 选择的编号大，那么女性 $a$ 和女性 $b$ 就叫做一对不稳定因素。

由于每个女性选择的男性是有一定的随机性的，所以不稳定因素的数目也是有一定随机性的。JYY 希望你能够求得不稳定因素的期望个数（即平均数目），从而进一步研究为什么速配算法不能满足大家的需求。

为庆祝疫情防治取得重大进展，某商场举行酬宾活动，给顾客一些优惠额度，规则如下：

1. 每位顾客可以任意选择一个整数作为自己的幸运数字。
2. 每位顾客的初始优惠额度为 $0$ 元。
3. 商场有 $n$ 个奖励条件，对应不同的奖励额度 $w_i$ 。
4. 每位顾客需要依次比对这 $n$ 个奖励条件，如果该位顾客选择的幸运数字满足第 $i$ 个条件，那么他的优惠额度就会异或上这个条件所对应的奖励额度。

奖励条件共有三种，假设顾客选择的幸运数字为 $x$：

1. 区间型条件，其有两个参数 $L$ 与 $R$，满足条件为 $L \le x\le R$ 。保证 $L < R$ 。
2. 相等型条件，其有一个参数 $A$ ，满足条件为 $x = A$ 。
3. 不等型条件，其有一个参数 $B$，满足条件为 $x \neq B$ 。

小炎同学获知了所有奖励条件的信息，他希望知道一位顾客能够得到的最大优惠额度以及对应的幸运数字是多少，请你帮他计算。

小 $A$ 是 $B$ 公司的一名 $PM$(product market) 。$B$ 公司越来越注重产品使用情况分析，而小 $A$ 的工作就是整天对着一堆数据分析来分析去，没完没了。其中有一个操作是小 $A$ 很头疼的，就是要把多个 $csv$文件的数据拷到同一个 $excel$ 文件中去。 有一天小 $A$ 满怀期待地找到了你，一个高级程序员，她想让你写程序帮她完成这个简单重复性工作。这不是坑爹吗，直接操作 $excel$ 还要用到第三方的库，还不如直接写到 $csv$ 文件中，让她再手动去转成 $excel$ 文件。经过内部沟通协调，最终定下了这个方案。 $csv$ 是一种 $excel$ 可支持和格式，且存储方式非常简单。它实际上就是用“,”来分隔相邻的两个列。比如以下三行数据：

1
2
3

a,a,a
b,,b
,c,c

表示的就是：

现在小AA想做的就是把各个文件按照从左往右的顺序拷到同一个文件当中。比如文件aa的数据是：

1
2

a1,b1,c1
a2,b2

文件bb的数据是：

1
2
3
4

a1,b1,c1,d1
a2,b2
a3,b3,c3
a4

那么她所希望的最终结果是：

这个结果在csvcsv文件里就是：

1
2
3
4
5

a,,,b,,,
a1,b1,c1,a1,b1,c1,d1
a2,b2,,a2,b2,,
,,,a3,b3,c3,
,,,a4,,,

以上结果的第一行是每一个文件的文件名，文件名与相应文件的第一列对齐。如果相应文件不止一列，那么其它列用空的单元格来补充。
输入的 $csv$ 文件里保证了每一行的末尾都没有“,”，也就是说像 $a$ 文件的第 $2$ 行的第 $3$ 列一样，如那一格是空的，那么在$b2$ 后面是没有“,”的。
输出的 $csv$ 文件里因为是程序的输出结果，为了简化程序，如果末尾是空的，那么还是会显式输出“,”，如以上的结果所示。
输入文件保证至少有一行一列非空。
输出的文件要保证下一个文件的第一列要紧邻着上一文件的最后一个非空列的右面。最后一个文件只输出到最后一个非空列。

给定一个 $n$ 个节点，$m$ 条边的图无向图。求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。

现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！

小皮球只会玩 $\text{N}$ 个英雄，因此，他也只准备给这 $\text{N}$ 个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。

这 $\text{N}$ 个英雄中，第 $\text{i}$ 个英雄有 $K_i$ 款皮肤，价格是每款 $C_i$ Q 币（同一个英雄的皮肤价格相同）。

为了让自己看起来高大上一些，小皮球决定给同学们展示一下自己的皮肤，展示的思路是这样的：对于有皮肤的每一个英雄，随便选一个皮肤给同学看。

比如，小皮球共有 $5$ 个英雄，这 $5$ 个英雄分别有 $\text{0,0,3,2,4}$ 款皮肤，那么，小皮球就有 $3 \times 2 \times 4 = 24$ 种展示的策略。

现在，小皮球希望自己的展示策略能够至少达到 $\text{M}$ 种，请问，小皮球至少要花多少钱呢？

给定一个 $n$ 个点， $m$ 条边的食物网，求出其中食物链的个数。注意单独的一种孤立生物不算一条食物链。

Emiya 是个擅长做菜的高中生，他共掌握 $n$ 种烹饪方法，且会使用 $m$ 种主要食材做菜。为了方便叙述，我们对烹饪方法从 $1 \sim n$ 编号，对主要食材从 $1 \sim m$ 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya 会做 $a_{i,j}$ 道不同的使用烹饪方法 $i$ 和主要食材 $j$ 的菜 $(1 \leq i \leq n,1 \leq j \leq m)$ ，这也意味着 Emiya 总共会做 $ \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} a_{i,j}$ 道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 $k$ 道菜的搭配方案而言：

• Emiya 不会让大家饿肚子，所以将做至少一道菜，即 $k \geq 1$
• Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同
• Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即 $\lfloor \frac{k}{2} \rfloor$ 道菜）中被使用

这里的 $\lfloor x \rfloor$ 为下取整函数，表示不超过 $x$ 的最大整数。

这些要求难不倒 Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。

Emiya 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数 $998,244,353$ 取模的结果。

Byteburg市东边的建筑都是以旧结构形式建造的：建筑互相紧挨着，之间没有空间。它们共同形成了一条长长的，从东向西延伸的建筑物链（建筑物的高度不一）。Byteburg市的市长Byteasar，决定将这个建筑物链的一侧用海报覆盖住，并且想用最少的海报数量，海报是矩形的。海报与海报之间不能重叠，但是可以相互挨着（即它们具有公共边），每一个海报都必须贴近墙并且建筑物链的整个一侧必须被覆盖（意思是：海报需要将一侧全部覆盖，并且不能超出建筑物链）。