先拓扑排序建立一棵有根树。对于每个节点，存一个区间表示取值这段区间内答案最优。然后每次sort儿子中限制后合并即可。时间复杂度O(nlogn)

原题:bzoj4297

先考虑k≤8，字典序类问题使用逐位确定。状态为使用过的几种字符分别使用了多少次，状态数≤(k +1)!。预处理时需要再记录前一个使用的是哪个字符。

当k>8时，每次输出一串形如ababab...baba的前缀，可以把k减小2。

果然字符串的终点和字符串没什么关系吗。

不难发现我们每次只会在一个长竹竿后面拼接一个基础的短竹竿来增加长度。假设每次拼接竹竿的重叠部分为 $p$，显然 $p$ 是字符串的一个 border。

我们可以把这个字符串的所有 border 求出来，得到一个大小为 $m$ 的集合 $\{b_i\}$。最后要求的就是满足 $v\in [0,w-n]$，且方程 $\sum_{i=1}^m b_ix_i=v$ 存在解的 $v$ 的数量。

好的，后面是一个经典的同余最短路问题，于是我们得到了一个 $\min{b_i}\times n$ 的解法，但是这个做法是 $O(n^2)$ 的。

考虑优化这个做法，经典结论是一个字符串的 border 可以划分成 $\log n$ 段等差数列 $d_i+c_il_i$（结论证明较为复杂）。考虑对于每一个 $i$，求出在 $\bmod d_i$ 意义下，加入前 $i$ 个等差数列对应的边后的最短路。

依次加入每个等差数列，计算对最短路的影响。先考虑将原来 $\bmod d_{i-1}$ 意义下的最短路换成 $\bmod d_i$ 意义下的最短路，设前后两者对应的最短路数组为 $f_i,g_i$，可以用 $f_i+kd_{i-1}$ 去更新 $g_{(i+kd_{i-1})\bmod d_i}$，其中 $k$ 是没有限制的。

可以看成每个点 $i$ 向 $(i+d_{i-1})\bmod d_i$ 连一条有向边，这样整个图显然会划分成 $\gcd(d_{i-1},d_i)$ 个环，每个环之间独立。这样就很好做了，断环成链复制一遍，然后用环上上一个位置更新当前位置，总复杂度 $O(n)$。

转化完模数后，考虑用 $g_{i}+kc_i$ 去更新 $g_{(i+kc)\bmod d_i}$，其中 $k\in [0,l]$，还是可以看成每个点 $i$ 向 $(i+c)\bmod d_i$ 连一条有向边，划分成 $\gcd(d_i,c)$ 个环，但只能转移一次，最多从前 $l$ 个位置转移，单调队列 $O(n)$ 即可。

这样时间复杂度为 $O(Tn\log n)$。

先考虑一下朴素的 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!}x^j$$

实际上是将 $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)$。

好像是 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分了