这么快就 2020 了，回想我第一次参加省冬是初一的事（虽然那时听不懂几题）。
今年我就要参加 FJOI 了，虽然知道自己没啥戏，但还是认真一把。
今年我就要参加中考了，真是丢人啊。
今年我就要成为高中生了，在创新班会被踩的呀。
回头一想，2019 真是好长的一年，那些记忆中的事情，总觉得是发生在一两年前。
2019 又是丢人的一年。由希望变为失望，大概比没有希望过要好吧。
省冬时不好好上课，现在一时兴起，想写写省冬的题解。
学习兔巨神，红的是主要看题解的，绿的是主要自己想的。（安慰自己，省选难度的题，看题解是正常的，是正常的……）
D1T1 life
这天一题都没写，爆零了……
题意：有一个 (n) 个点的有向图，每个点可以是黑或白的，边只能从小往大连。相邻点不同色的路径称为交错路径。给出每个点是黑 / 白 / 未确定的，要给未确定颜色的点确定颜色，并确定每条边是否存在，求出交错路径条数为奇数的方案数，模 (998244353)。
记 (g_i) 表示以点 (i) 为终点的路径条数的奇偶性。
记 (f_{i,j,k}) 为已经到了点 (i) ，已有 (j) 个白点的 (g) 为 (1)，(k) 个黑点的 (g) 为 (1) 的方案数。
把 (i+1) 染白的转移：
(f_{i+1,j,k} leftarrow f_{i,j,k}2^{i-k}c(k,1))
(f_{i+1,j+1,k} leftarrow f_{i,j,k}2^{i-k}c(k,0))
把 (i+1) 染黑的转移类似。
其中 (c(k,d)) 表示从 (k) 个点中选出若干个点向当前点连边，点个数奇偶性为 (d) 的方案数。
答案就是 (sum_{(j+k)mod 2=1}f_{n,j,k}) 。
注意到当 (k>0) 时， (c(k,d)=2^{k-1})，故此时 (2^{i-k}c(k,d)=2^{i-1})；
而 (k=0) 时，(2^{i-k}c(k,1)=0)，(2^{i-k}c(k,0)=2^{i})。
所以只要在 dp 中记 (k) 是否大于 (0) 以及 (j) 是否大于 (0) 。
但发现这样答案统计不了了。加一维状态表示当前路径条数的奇偶性即可。
后面三维状态都是 (0) 或 (1)，故总复杂度为 (O(n))。
D1T2 winner
我测试结束后在食堂听到个“容斥套容斥”，立马就会了，假装主要是自己想的……
题意：有一个 (n) 个点 (m) 条边的简单无向图，要给边定向，使得存在一个点 (T) 使得 (1) 号点和 (2) 号点都能到达它，求方案数，对大质数取模。
考虑算出不合法方案，再用 (2^m) 减。
枚举 (1) 号点和 (2) 号点所能到达的点集 (A) 和 (B)，由于不合法，容易想到
- (Acap B=varnothing)；
- 不应存在边 ((u,v)) 使得 (uin A,vin B)；
- 对于 ((u,v)) 满足 (u otin Acup B,v otin Acup B)，这条边怎么定向都可以；
- 对于 ((u,v)) 满足 (u otin Acup B,vin Acup B)，这条边的方向只能是从外向里；
现在只剩下点集内部的处理了，考虑预处理每个点集内部的答案。
我们使用一个 DP 来解决，记 (f_{1或2,I}) 表示从 (1) 或 (2) 号点开始，能走到的集合恰好为 (I) 的方案数，转移时拿总数去掉子集的答案即可。
处理时要小心。
枚举两个不相交子集是 (O(3^n))，枚举子集的子集是 (O(3^n))，所以总时间复杂度是 (O(3^n))。
代码里面似乎多个快速幂的 (log)，这是可以预处理的。
D1T3 brr
这是 nb 字符串题。
题意：有一个长度为 (n) 的字符串，你要选出其若干段不相交的子串，使得选出来的这些串中，下一个是上一个的严格子串。求最多能拿出来多少段。
第一个结论：一定存在一种最优方案，最后一串长度为 (1) ，倒数第二串长度为 (2)，以此类推。
证明显然。
于是就想到从后往前 DP，可以记 (dp_{i,j}) 表示选出子串 ([i,i+j-1]) ，其后能不能选出 (j-1) 段使满足题意。可以枚举下一串与 ([i,i+j-2]) 相等还是与 ([i+1,i+j-1]) 相等来转移。
显然每一串长度为 (O(sqrt n)) 级别，所以这是 (O(nsqrt n imes)判断复杂度()) 的。
然后是更骚的结论。
大概是，如果子串 ([i,i+j-1]) 之后能选出 (j-1) 段，那么 ([i,i+j-2]) 之后一定能选出 (j-2) 段， ([i+1,i+j-1]) 之后也一定能选出 (j-2) 段。
直观理解如下图，其中红色为删去的。
于是你发现，刚才那个 (dp) 数组一定是一段 (1) 然后一段 (0) 然后没了。只要记录 (dp_i) 为从 (i) 开始最多能拿出来多少段。
由刚才那个结论可以推得，(dp_ile dp_{i+1}+1)，于是我们可以利用类似后缀数组求 height 的方法边推边判断。用喜欢的数据结构快速判断即可。
我是先建 SA ，然后 二分 + ST表 维护与 (i) 的 LCP 大于等于某个数的区间，zkw线段树维护 DP 值。时间复杂度 (O(nlog n))。
D2T1 building
神仙贪心，不会证明。
题意：有一个长度为 (n) 的数列，原先每一个位置都是 (0)。每一次，我们可以给两个相邻的位置分别 加一 和 加二 。问最少需要操作多少次，才可以使得对于 (1 ≤ i ≤ n)，第 (i) 个位置上的数大于等于 (h_i)。
从左到右贪心，让第 (i) 个位置尽快填满，显然是在第 (i) 个位置能多填就多填。
考虑以下三种反悔——
（把一个 加三 反悔掉就是取消之前的反悔）
然后从左往右填，优先填最大的 加六，然后填 加三，然后填 加二，最后根据奇偶性决定。
D2T2 bracelet
考场上过了。
题意：给定一个长度为 (n) 的手链，对于每一个珠子，可以不染色，也可以染 (m) 种颜色中的一种。不能有相邻的两个珠子同时被染色。问不同的染色手链种类数。旋转相同视作一种。对大质数取模。
暂时不管旋转相同，看看怎么算……又发现首尾不能都染色这个很难搞，暂时不管这个要求。
那么有一个显然的递推，答案是 (g_i=g_{i-1}+mg_{i-2})，边界条件 (g_0=1)，(g_1=m+1)，这个东西可以矩阵快速幂优化。
开始考虑首尾不能都染色的条件，就有所有方案去掉强制让首尾都染色的方案。即 (f_i=g_i-m^2g_{i-4})。(i<4) 时特殊处理就好。
这个旋转相同用 Burnside 引理搞一下就好了。
时间复杂度 (O(sqrt nlog n))。
D2T3 number
考场上过了。
题意：维护一个正整数可重集，每次插入或删除一个数，输出最大公因数为一个质数 (k) 的正整数的对数（(k) 是定值）。
首先发现这个 (k) 是个鸡肋，输入的时候是 (k) 的倍数就除以 (k)，不是就扔掉就好了。转为求互质对数。
xjb 推一下：(sum_{1le i< jle n}[(a_i,a_j)=1]=sum_{d=1}^{z}mu(d)C_{c(d)}^2)
其中 (c(d)) 表示集合中为 (d) 的倍数的个数。
线筛 (mu(d))，每次修改的时候枚举所插入 / 删除的数的约数暴力改 (c(d)) 即可。复杂度 (O(z+qsqrt z))，其中 (z) 为集合里数的最大值。
D3T1 hunting
大分类讨论。要不是我校 OJ 有这题，我就爆零了。
题意：给一棵 (n) 个结点的数，(q) 次询问，每次给出 (a,d_a,b,d_b)，要你输出一个点，使得这个点到 (a) 的距离为 (d_a)，到 (b) 的距离为 (d_b)，或者输出无解。
就是个恶心的分类讨论，写写长剖倍增树上 DP 什么的就行，复杂度 (O(nlog n))，可以通过各种离线操作优化到 (O(nalpha(n)))。
D3T2 graph
这题之前见过，但考场上光写 T1 了。
它长得比较丑，大概就是转成，求出所有方案的 (2^c) 之和模 (4)，而 (2^c) 又可以转成相邻必须同色的黑白染色方案数之和。
D3T3 string
又出大码题了。
题意：两个字符串是相似的，当且仅当存在至多一个 (i) ，使得这两个字符串中只有第 (i) 个字母不同。有一个长度为 (n) 的字符串，问，对于每个长度为 (m) 的子串，有多少个其它长度为 (m) 的子串与它相似。
两个字符串相似当且仅当 (LCP+LCSge m-1)。
(LCP) 是后缀树 (LCA) 的深度，(LCS) 是前缀树 (LCA) 的深度。
转换成有多少对 ((u,v)(u<v))，使得 (dep_{LCA_1(u,v)}+dep_{LCA_2(u,v)}ge m-1)。
在一棵树上 DSU ON TREE，在另一棵树上统计，用数据结构搞一搞，挺难弄的。
D4T1 hakugai
这天的题好丧……
这题也比较丑，大概是发现所求数列其实可以看做斐波那契数列里面抽出的某些项，而斐波那契数列的循环节是可以算的，然后就会了。
没写代码
D4T2 kaisou
题意：有一棵 (n) 个结点的树，你要给它去掉 (k) 条边再加上 (k) 条边，使得它还是棵树。求能得到多少不同形态的树，两棵树不同当且仅当存在一条边 ((u,v)) 在一棵树中出现，而在另一棵树中不出现。
标算是一个有趣的矩阵树定理 + 插值，复杂度是 (O(n^4)) 的，但是有一个 (O(n^2)) 的做法。
首先有一个结论：对于 (n) 个点 (m(m>1)) 个联通块的森林（点有标号），设第 (i) 个联通块大小为 (v_i)，则加上 (m-1) 条边把这些联通块连成一棵树的方案数为 (n^{m-2}prod v_i)。
PinkRabbit 用生成函数证明了，而 lzy 给出了一个非常直观的证明：
定义一个连通块的编号为其中最小的结点的编号。
对于像这样一个由连通块构成的树，我们构造一个类似于 Prüfer 序列的 序列，构造方法是，每次找到编号最小的度数为 的 连通块 并删除，序列中添加与之相连的 结点 编号，重复执行直到只剩下 个连通块。
考虑还原的过程，我们找到 序列中最靠前的 结点 ，把它和 其中结点都未在 序列中出现的编号最小的 连通块 连边，但是我们并不知道要向那个连通块的哪个结点连边，所以还需要添加每个连通块被删除前，它所连出的那条边在哪个结点上的信息，我们把这称为 序列。
这时我们发现，根据 序列和 序列，可以唯一确定一种方案，并且在各连通块大小给出的情况下，任何方案都能得到一个 序列和 序列，任何合法的 序列和 序列都能还原出一种方案。
根据定义，我们发现， 序列和 序列的组合一共有 种，故方案同样有 种。
接下来就好做了，记 (f_{u,j}) 表示 (u) 的子树内所有只保留 (j) 条边的方案的连通块大小乘积和，做一个树上背包，然后按照前置结论计算。
发现求出来的答案不是想要的，这是因为在你算保留 (j) 条边的方案数的时候，可能有些边被切掉完又连回来了，导致一些东西计算多次。根据套路，二项式反演然后 NTT 容斥一下就好了。
D4T3 atoranta
看完题解发现这题还是不错的。
题意：有一棵 (n) 个点的有边权的树，(q) 次修改某一条边的边权，要回答在初始局面和每次修改后，有多少条无向路径 ((u,v)) 满足路径上所有边的 (gcd) 恰为 (1)。
记 (w) 为权值，(k) 为边权的质因数个数，(d) 为边权的约数个数。
假设已求出了初始状态的答案，每次修改，改变的只有跨过修改边的路径。
可以记 (g_u) 为从 所修改的边 到 点 (u) 的路径上所有边的 (gcd) ，暴力求出 (g)，并把修改边左侧和右侧的 (g) 用两个桶 (b_l) 和 (b_r) 来存，暴力拼接。
求一次 (g) 的总复杂度为 (O(nlog w)) （(log) 是求 (gcd) 的消耗），拼接复杂度为 (O(d^2))，(q) 次修改，所以这部分的总复杂度为 (O(qnlog w+qd^2))，由于前一部分实际上不满，所以是可以接受的。
莫比乌斯反演一下，答案是 (sum_{i=1}^wmu(i)f(i)) ，(f(i)) 为有多少条路径上所有边都为 (i) 的倍数。
考虑对每个 (i) ，用并查集维护只有 (i) 的倍数的边时每个连通块的大小。每个边只会被搞它的约数个数次。
又发现 (mu(i)=0) 的时候是没有贡献的，所以可以把这部分剪掉，那么每条边只会被搞 (2^k) 次，这个复杂度为 (O(2^knalpha(n)+wlog w))，(wlog w) 为枚举 (i) 的所有倍数的消耗。
然后就可以做了。
总时间复杂度大概是 (O(qnlog w+qd^2+2^knalpha(n)+wlog w))，可以接受。
D5T1 rng
早上起不来，十点才开始写代码，常数巨大，拍都没拍，测试时竟然过了。
题意：有一个长度为 (n) 的序列 (a_1, a_2, cdots, a_n) ，(a_i) 为在 (left[ l_i, r_i ight]) 中独立均匀随机生成的实数，求这个序列逆序对个数的期望值，对 (998244353) 取模。
虽然题目里说是实数，但我们先按整数来算吧。
答案是
(sum_{i=1}^nsum_{j=1}^{i-1} P(a_j>a_i))
(=sum_{i=1}^nsum_{x=l_i}^{r_i} P(a_i=x)sum_{j=1}^{i-1}P(a_j>x))
(=sum_{i=1}^n frac{1}{r_i-l_i+1}sum_{x=l_i}^{r_i}sum_{j=1}^{i-1}P(a_j>x))
记 (t_x = sum_{j=1}^{i-1}P(a_j>x))。
思路大概是从 (1) 到 (n) 扫一遍，每到一个点，求一下 (sum_{x=l_i}^{r_i}t_x) 计入答案，然后更新 (t_x)。
注意到 (P(a_j>x)=frac{r_j-x}{r_j-l_j+1})。
所以维护 (t_x) 相当于维护一个区间加等差数列，区间求和的数据结构，可以用树状数组 / 线段树等你喜欢的数据结构来解决，时间复杂度 (O(n log max{r_i}))。
但是你写完会发现答案不对，因为题目告诉你，(a_i) 是实数，稍微改一改就好了。
D5T2 lg
题意：给出 (n,m) ，计算 (displaystyle left(prod_{x_1 , x_2 , cdots , x_n in [1,m]} operatorname{lcm}left(x_1 , x_2 , cdots , x_n ight) ^ {gcdleft(x_1 , x_2 , cdots , x_n ight)} ight) mod 998244353)。
推式子水平有待提高。
式子很多，不想列出来，说重点：
1.用 (varphi) 把指数上的 (gcd) 去掉；
2.枚举质因子算贡献；
3.(max{k_i}=j) 的方案数等于 (forall i,k_i< j+1) 的方案数减去 (forall i ,k_i< j) 的方案数。
时间复杂度可以容易的分析出是 (O(mlog mlog n)) 的，但仔细分析可以得出 (O(mlog n))。
D5T3 pm
题意：有一个 (1) 到 (n) 的排列，你需要把它排序。你要进行两个阶段的操作。第一阶段中，每次任选两个相邻元素并进行交换。第二阶段中，每次修改一个位置上的元素。最小化两个阶段操作的总次数，并给出一种总操作次数最小的合法方案。
这是好玩的结论题。同学有 NB 贪心做法，实在是理解不能。
把交换过的位置连上边，则序列中有若干个有边的段。
对于一个长度为 (l) 的段，显然至少有 (l-1) 次交换。因为交换次数大于等于 (l) 可以直接第二阶段解决，所以交换次数恰为 (l-1)。
考虑一个区间想要成为一个段，一定要满足以下条件：
1.区间和值域相同；
2.可以通过 (l-1) 次交换排好序。
结论 1：两个合法的区间要么不相交，要么一个是另一个的子区间。
证明显然。
结论 2：如果一个这样的区间包含另一个，那么选里面那个就好了。
证明显然。
所以我们可以先对于每个右端点，求出满足条件 1 的最小区间，然后把求出来互相包含的处理掉，最后判断是否满足条件 2 即可。
对每个右端点求出满足条件 1 的最小区间，我们可以采用 hash 等；
判断是否满足条件 2 ，实际上类似 CSP2019 Day1T3 链上的情况，那题的某个 0 分贪心在这里是正确的。
代码很短，复杂度 (O(n))。