T1:

小 D 正在研究序列。

对于一个正整数序列而言，小 D 认为他是好的，当且仅当任意相邻两个数字均为一个奇数和一个偶数。

形式化地，对于一个序列 $b1, b2, · · · , bm$ 而言，小 D 认为他是好的，当且仅当对于任意 $1 \le i < m$，有 $b_i$ 为奇数且
$b_{i+1}$ 为偶数，或 $b_i$ 为偶数且 $b_{i+1}$ 为奇数。

小 D 得到了一个长度为 n 的序列 $a1, a2, · · · , an$，小 D 想要通过重新排列它，使它变为一个好的序列。小 D 定义一种重新排列方案的代价为重排后每个数字位置差的绝对值之和。小D 想要最小化重排的代价。

此外，小 D 还想在最小化重排代价的基础上，最小化结果序列的字典序。但是小 D 并不会，请你帮帮他。

题解1

实际上奇数和偶数是独立的,我们可以考虑其中一种,另一种自然就会了.那么我们比较容易得到,在不考虑字典序的情况下,我们只需把所有奇数顺序不变,放在各个奇数(偶数)位置上.那么如果考虑字典序怎么办呢?显然是需要对顺序做一些安排.我们假设有两个数在$X,Y$,要放到$A,B$,其中$X< Y< A< B$.那么如果我们把X放在A位置,代价就是$A-X+B-Y$.如果把$X$放在$B$位置,代价就是$B-X+A-Y$.都是$A+B-X-Y$,所以换顺序代价.而方向不同的换顺序就会出现交叉,显然代价会变大.所以对于一段方向都向左的情况,我们从小到大排序,从左往右放.向右同理.

T2:

小 D 得到了许多灯泡。
这些灯泡共有 n 个，小 D 把它们排成了一行，并依次编号为 $1, 2, · · · , n$。这些灯泡有许多不同的颜色，小 D 把颜色依次编号为 $1, 2, · · · , k$，则第 i 个灯泡
的颜色为 $c_i$。

初始时，所有灯泡都是灭的。小 D 每次操作会把某一种颜色的灯泡全部翻转状态，即从亮变灭或从灭变亮。在每次操作完后，小 D 想要知道有多少极长的亮灯区间。

形式化地，我们称一个区间 $[l, r]$ 是极长的亮灯区间，当且仅当编号为 $l, l + 1, l + 2, · · · , r$ 的灯都是亮着的，而编号为 $l − 1$ 以及 $r + 1$ 的灯要么不存在，要么是灭着的。

但是小 D 并不会，请你帮帮他。

题解2

本题用到了一种技巧:根号分治.我们可以把这道题抽象成一个图的问题.点对应序列中亮起的点,边只在相邻的亮着的灯连起来.这样的话由于无环,点数一定比边数多1.因此我们知道,联通块数等于亮着的灯数-相邻亮着的点之间的边数.

点数可以直接在输入的时候进行维护.而边数可以通过分块(分类来完成).我们可以把每一个颜色连续的部分压成一个点,向相邻颜色连边,建立另外一张图.我们假设有一个阈值B,根据灯泡出现次数$deg[u]$和B的关系分类.比如我们现在把一个点u点亮.如果它是一个大点,那么大点不超过n/B个,我们就暴力去搞.如果是一个小点就不好暴力,那么我们反过来想.当我们改变一个小点u的时候它周围的点v必须是on才对答案有贡献.也就是v被修改过.从u考虑不好考虑,所以我们修改v时找到周围的u,使其标记+1,代表下次修改u时答案会+1.

T3:

小 D 正在研究一场锦标赛。
这场锦标赛共有 n 位选手参加，他们被依次编号为 $1, 2, · · · , n$。选手两两之间会进行一场比赛，在两名选手比赛时，编号较小的那个有 $p$ 的概率取胜，而较大的那个有 $1 − p$ 的概率取胜。换言之，对于选手 $i, j(i < j)$之间的比赛，有 p 的概率是选手 i 获胜，而剩余的概率是选手 j 获胜。

最终，锦标赛主办方会给其中若干选手颁奖。为了显得公平公正，主办方需要保证这些人胜过了其余的所有人。形式化地，若主办方给集合 $S$ 中的选手颁奖，则主办方需要保证对于任意 $i ∈ S$ 和 $j \notin S$在 i 和 j 的比赛中是 i 胜出。

小 D 想要知道，对于每个 $1 ≤ k < n$，最终主办方可以给 k 个选手颁奖的概率是多少。具体的输出方式请见输出格式部分。

但是小 D 并不会，请你帮帮他。

输出格式

为了避免太大规模的输出，设 $v_k$ 表示最终可以给 k 个选手颁奖的概率，定义函数 $f(k)$ 满足 $f(1) = 1$，而 $f(i) = (f(i − 1))^2 + 2$，设 $V =\sum_{k=1}^{n-1} v_k · f(k)$，则你只要求出 $V$ 的值即可。

为了避免浮点数精度误差，可以证明 $V$ 可以写成 $\frac{x}{y}$ 的形式，则你只要输出 $x ·y^{-1} mod M$ 的值即可，其中 $M = 998244353(= 223 × 7 × 17 + 1$).

题解3

对于某个K,只要存在一个大小为k的集合,那这个集合一定是唯一的.因为如果可以更换一个人的话,胜负关系会矛盾.

如果我们考虑$F(n,k)$表示$n$个人中有$k$个人得奖的概率.当我们推到$n+1$的时候,我们可以考虑两种情况:如果$n+1$在集合内,那就要赢过集合外的所有人,如果在集合外,那就要输给集合内的所有人.而其他人编号都比$n+1$小.所以我们有:
$$
F(n+1,k)=F(n,k)\times p^k+F(n,k-1)\times q^{n-k+1}\ \ (q=1-p)
$$
然而只有一个式子是求不出递推式的.我们还可以从1的角度考虑.如果1在集合内,那就赢过集合外所有人.如果1在集合外,就输给集合内所有人,而所有人编号都比1大.所以我们又可以得到:
$$
F(n+1,k)=F(n,k)\times q^k+F(n,k-1)\times p^{n-k+1}
$$
两个式子联立就可以消去$F(n+1,k)$,整理得到:
$$
F(n,k)\times (p^k-q^k)=F(n,k-1)\times (p^{n-k+1}-q{n-k+1})
$$
当然了初值为$F(n,0)=1$,所以在$p\neq q$也就是$p\neq \frac{1}{2}$时我们可以$\Theta(n)$算出答案.我们选择1,n这两个位置的原因是其他点的序号都比这个点大或者小,所以可以计算,否则不知道集合中的人是哪些,无法计算.

接下来就是$p=\frac{1}{2}$的情况了.这时任何人胜率都是$\frac{1}{2}$,所以我们选出k个人作为最后的胜者,则有
$$
F(n,k)=C^k_n\times \frac {1}{2^{k(n-k)}}
$$
时间复杂度都是$\Theta(n)$或者$\Theta(nlog_2n)$

——Gensokyo