先考虑一下朴素的 dp。

不难发现，对于一个集合最重要的是集合里最小的元素，剩下的元素对应的 $a_i$ 都大于这个值，可以考虑把所有值按照从大到小排序，则集合里其他元素都在最小元素之前。

对于第 $i$ 个数，考虑这个数是集合里最小的元素，或不是最小的元素对应的方案数。 $dp_{i,j}$ 表示 $1\sim i-1$ 个数处理完后，还剩下 $j$ 个数未确定属于哪个集合的方案数。

若第 $i$ 个数不是集合里最小的元素：

$$dp_{i+1,j+1}\gets dp_{i,j}$$

若第 $i$ 个数是集合里最小的元素，枚举这个集合里还有几个元素，即：

$$dp_{i+1,j-k}\gets dp_{i,j}\times \text{C}_j^k(0\le k<a_i)$$

初始状态为 $dp_{1,0}=dp_{1,1}=1$，目标状态为 $dp_{n+1,0}$。转移的过程中对于第二类转移需要枚举 $k$，复杂度为 $O(n^3)$。

考虑如何优化这个 dp 的第二类转移，将组合数拆开得到：

$$dp_{i+1,j-k}\gets dp_{i,j}\times \frac{j!}{k!(j-k)!}$$

假定对于阶段 $i$，设有

$$F(x)=\sum_{i>0}dp_{i,j}j!x^j$$

$$G(x)=\sum_{i>0}\frac{1}{k!}$$

实际上是将 $F,G$ 做一个减法卷积的到 $H$，则有

$$H(x)=\sum_{i>0}dp_{i+1,j}j!x^j$$

对于减法卷积，可以翻转一个多项式的次数，此时减法卷积就转化成了加法卷积，直接用 NTT 计算即可。

可以选择为 $dp_{i,j}$，也可以直接维护 $dp_{i,j}\times j!$。算法的复杂度为 $O(n^2\log n)$。

先考虑 $O(nq)$ 做法。枚举每个点为根去 DFS 做 dp。

不难发现两个相邻的点不能操作二，所以状态要设 $f_{i,2}$ 表示点 $i$ 操作二，把子树的边覆盖完的最小操作。

若一个点不进行操作二，则他到子节点需要用操作一来覆盖，而一个操作一可能端点在两个儿子。考虑先把这个操作一的链拆开，然后从儿子向上合并时去匹配。设 $f_{i,1},f_{i,0}$ 表示点 $i$ 进行操作二，覆盖后子树内留下一个到儿子的操作一半条链没有匹配或全部匹配完。

然后考虑 dp 转移，分类讨论即可：

$$f'_{x,0}\gets \min(f_{x,0}+f_{y,2},f_{x,1}+f_{y,0},f_{x,1}+f_{y,1}-1)$$

$$f'_{x,1}\gets \min(f_{x,1}+f_{y,2},f_{x,0}+f_{y,1},f_{x,0}+f_{y,0}+1)$$

$$f'_{x,2}\gets f_{x,2}\min(f_{y,0},f_{y,1})$$

然后直接转移就可以，复杂度为 $O(nq)$。

考虑换根出答案？但是这个贡献形式比较难拆开，考虑用矩阵描述 dp 的转移，这样做前缀后缀的转移就转化为求矩阵前缀后缀积了，本来矩阵乘法需要严格控制顺序，但这个东西先合并那个子节点无所谓，所以瞎做就行。

复杂度为 $O(nV^3)$，其中 $V=3$。

好像是 COGS 首 A，写篇题解。

其实这道题的思维难度不是特别大，只需要一些技巧和比较高级的算法即可解决。

思路分析

注意到对于一对用来替换的字符串二元组 $(s,t)$，若 $s=t$，则这对字符串一定没用，题目已经限制。

对于这对 $s,t$，可以分别将其表示成 $s=s_A+s_C+s_B,t=t_A+t_D+t_B$，其中 $s_A,t_A$ 是 $s,t$ 的最长公共前缀，$s_B,t_B$ 是 $s,t$ 的最长公共后缀，每次替换操作，实际上是将一个字符串中的 $s_C$ 替换成了 $t_D$。

对于一对询问的字符串 $(S,T)$，若长度不相等，则一定没有合法的变化，题目已经限制。

依然求出两个 $S,T$ 的子串 $s_{A,C,B},t_{A,D,B}$（意义同上），若 $(S,T)$ 可以用过 $(s,t)$ 替换得来，必须满足 $S_C=s_C,T_D=t_D$，且 $s$ 在 $S$ 中出现，$t$ 在 $T$ 中出现。

这样的话，我们就可以得到一个 $O(nq)$ 的算法，对于每个变化的字符串二元组和询问，处理出变化的部分，若 $(s,t),(S,T)$ 变化的部分一样，且 $s$ 再 $S$ 中出现，$t$ 在 $T$ 中出现，因为变化的部分要匹配上，所以匹配的起始位置是确定的，可以用字符串 Hash 来完成 $O(1)$ 的判断。

cin>>S>>T;int ans=0;
if(S.size()!=T.size()){
    printf("0\n");
    continue;
}
int L=0,R=S.size()-1;
while(S[L]==T[L])L++;
while(S[R]==T[R])R--;
for(int j=0;j<S.size();j++){
    if(j){
        hs[j]=hs[j-1]*P+S[j];
        ht[j]=ht[j-1]*P+T[j];
    }else{
        hs[j]=S[j];
        ht[j]=T[j];
    }
}
for(int j=1;j<=n;j++){
    bool flag=0;
    if(l[j]==-1)continue;
    if(R-L+1!=r[j]-l[j]+1)continue;
    int ll=L-l[j],rr=ll+len[j]-1;
    if(ll<0||rr>=S.size())continue;
    if(askS(ll,rr)!=a[j])continue;
    if(askT(ll,rr)!=b[j])continue;
    ans++;
}
printf("%d\n",ans);

考虑优化这个过程，离线，还是利用字符串 Hash，把变化部分相同的变化字符串和询问字符串放在一起处理。

此时变化部分的匹配一定满足，只需要保证 $s_A$ 是 $S_A$ 的后缀，$t_B$ 是 $T_B$ 的前缀。将所有 $s_A,S_A$ 放在一起建一个字典树，$t_B,T_B$ 放在一起建一个字典树，则前后缀关系可以转化成字典树上的祖先子孙关系，两个字典树就有两维的限制，直接做离散化加二维数点即可，复杂度为 $O(L+(n+q)\log(n+q))$。

这个做法所使用的算法均在提高级的考纲之内，应该是钦定的正解。

其实有一种更加优秀的做法，可以转化为经典的多模式串匹配的算法，但需要 AC 自动机。

考虑将每个字符串对 $(s,t)$ 拼成一个大串 $P=s_A+?+s_C+t_D+?+s+B$，其中 $?$ 是防止匹配的一个字符。把询问串也这样拼成大串 $Q$，每个询问就是有多少个 $P$ 是 $Q$ 的子串，直接 AC 自动机的复杂度为 $O(|\sum|L)$，其中 $|\sum|$ 是一个 $26$ 的常数。

后者实现比较简单，所以我只完成了第二个算法。

无法接受自己sT1T2没写出来

UPD 老师已经开大时间限制 已加上第二次评测的记录

我在写这篇题解的时候cogs上时间限制还是1秒，cogs评测机显然不符合CCFIntel Core Ultra 9 285K CPU @ 3.70 GHz的标准，在洛谷和云斗AC的代码，再加上卡常也88分，最慢的1.099s，所以我打扰了老师开大时限，但老师可能比较忙没有回复，所以这篇题解在cogs上的分数按照1s为准。

题意

给你一张$N$个点无向图，保证任意两个点之间都是联通的。

另外还有$K$个额外的点，你可以从这$K$个点里任意选择若干个点，选择第$j$个点的代价为$c_j$，然后对于每个选择的点都可以往原本$N$个点连无向边，第$j$个额外点对第$i$个原有点连边的代价为$a_{j,i}$。

现在求出这张图的MST。

$1 \leq N \leq 10^4$

$1 \leq M \leq 10^6$

$0 \leq K \leq 10$

思路

考场淘汰回放：

把T1当成dp死做半天做不出来之后看第二题，一眼看第二题，先写出了60分左右的解法，代码还写了半天，结果一直以为和最短路有什么关系，恶心半天写不出来了

40~60分

直接把所有的边放到图里，包括额外点的连边。

排序所有边之后，枚举选额外点的状态跑kruskal即可。

粗略估计时间复杂度$O(2^k * (M+NK))$（一共会有$M+NK$条边，枚举状态$2^k$）

不是满分，来看我回忆代码，不加赛时卡常，在cogs上就32分 云斗上80分 洛谷上88分

UPD:开大时间限制后cogs80分

http://218.28.19.228:8081/cogs/submit/code.php?id=7XieaPkPU

https://www.yundouxueyuan.com/record/69072490b8ccc474dc719cef

https://www.luogu.com.cn/record/245035597

100分

我们最终选的边肯定包括了不考虑额外点的最小生成树里，所以先对原图跑一遍最小生成树，只保留树边，然后再枚举状态跑kruskal其实就做完了。

时间复杂度$O(M log M + 2 ^ k * (N - 1 + NK))$

目前卡常在cogs88分，洛谷和云斗不卡常就是满分

UPD:100分了

太无聊了 写个水题题解吧（虽然赛时因为读错题被恶心了

题目大意

给你一个数组$A$，你需要选择若干个$A$中的**连续**段，使得每一段元素的异或和都是$K$。求最多选的段数。

$1 \leq n \leq 5 * 10^5$

思路

赛时没看到连续然后被卡半天

首先题目都说连续了，直接使用前缀和维护每一段的异或值，这里需要用到异或的逆运算，这里我手写了，实现很简单。

我们选择段的时候贪心的选，先把数组从前到后遍历一遍，还要维护一个set用来存储所有存在过的前缀异或值和一个总的异或值。

每次我们在set里查找一下有没有值满足对应的后缀能和当前的$a_i$匹配为$K$，我们记$a fxor b$为满足$b xor c = a$的$c$的值，那么我们就需要在set里查找$pre fxor (K fxor a[i])$，其中$pre$表示从最靠左的未匹配的位置到$i-1$之间所有元素的异或值。

如果在set里找到了符合条件的元素，也就是当前的$a_i$能够和一个后缀匹配成为一个异或和为$K$的连续段，那直接清空set，并把$pre$改为$0$，因为你后面考虑的就是下一段了，前面的就都不用管了，这样选的策略会让段的右端点尽量靠前就匹配，是最优的。

注意程序一开始要把set先插入一个$0$否则会WA

感谢ruyi为这篇题解作出的贡献。

题目大意

给你$N-K+1$个数，第$i$个数表示原数组$A$中第$i-K+1$到$i$的和。

现在问你有多少个01数组$A$满足上面的条件，保证至少存在一个$A$合法。

思路

我们发现$A$中的数取值只有$0$和$1$，不难想到给你的$N-K+1$个数里，相邻的两个数相差只有$0$,$1$和$-1$两种情况。

我们可以考虑维护一个数组$A$，初始化所有元素为$-1$，表示元素都没有确定。

如果相邻元素的差不是$0$，这两个元素的大小就是确定的，直接在$A$中修改；如果差是$0$，这两个元素就是一定相等的。

所以对于一个我们知道的相等的元素的集合，只要知道里面随便一个元素的值，整个集合都能确定，直接用DSU维护这个关系即可，实现很简单，实现很简单，直接把已知的$A_i$的值放到她的根节点上，再对于每个元素把她根结点的值放到自己上即可。

最后我们需要满足前$K$个元素是读入进来数组的第一个数，这堆连通块整体的方案数是$C(cnt1, s-cnt2)$，其中$cnt1$是我们连通块的数量，$cnt2$是我们确定的$1$的数量。

对.于后面的连通块，他们的取值怎么样都行，直接把答案乘$2$即可。

~~见过的最简单的一道蓝题（~~