T1 图书管理 (book)
考虑每个数做中位数的贡献，经典 trick 就是小于的为 \(-1\)，大于的为 \(1\)，前缀和相减为 \(0\) 的就合法，不会链表。
T2 两棵树 (tree)
又是经典 trick，森林的连通块数为点数减边数，证明就是算树的数量，好像之前见过这个 trick。
然后把贡献拆开，\(e\) 代表点，\(v\) 代表边，\(\text{E}((v_1-e_1)(v_2-e_2))=\text{E}(v_1v_2-e_1v_2-v_1e_2+e_1e_2)\)，每一项可以看成若干个 \(1\) 相加乘上若干个 \(1\) 相加，然后直接枚举节点算贡献即可。
- \(v_1v_2\)，\(T\) 中的 \(u\) 点在，则 \(U\) 中的 \(u\) 点一定不在，两个点的概率是 \(\frac{1}{4}\)，总贡献是 \(\frac{n(n-1)}{4}\)。
- \(e_1v_2,v_1,e_2\) 边数都是 \(n-1-d_u\)，三个点的概率是 \(\frac{1}{8}\)，总贡献 \(\frac{(n-1)(n-2)}{4}\)
- \(e_1e_2\)，直接枚举边 \((u,v)\)，然后减去 \(d_u+d_v\) 即可，如果 \((u,v)\) 在另一棵树中也有连边，就多减了一个，加 \(1\) 即可。
为啥把前面贡献直接算完后面循环算没有全循坏快，\(O2\) 给直接算完了？
T3 函数（fun）
自然地想到 01trie，对于异或完等于 \(b\) 的，直接找即可。
否则一定两边异号，如果第一个数异或完大于 \(b\)，找第一个小于 \(b\) 的位置即可，否则找第一个大于 \(b\) 的位置，这样它和前一个位置一定异号。
T4 编辑（edit）
原题：QOJ5312
编辑距离确实是一个专有名词，可以使用 LCS 的思想来求解，\(f_{i,j}\) 表示 A 串匹配到 \(i\)，B 串匹配到 \(j\) 的最小距离，转移如下：
然后枚举起点就可以做到 \(\mathcal{O}(n^3)\) 的复杂度，拿到 60pts。
发现上面的东西必须要以 \(n\) 为状态，几乎不可能优化，\(k\) 很小一定有作用，换一种思路，\(f_{i,j}\) 表示在 \(i\) 次编辑后，满足 \(S_{1\to x}\) 和 \(T_{st\to x+j}\) 的最大的 \(x\)，求得之后直接统计等于 \(|S|\) 的 \(f_{i,j}\) 即可。为什么要把 \(j\) 设计出来，可能在当前我不去匹配更优，所以类似与上面的式子，我需要知道两个串的具体位置，简单观察后发现，对于 \(f_{i,j},f_{i,j}+st+j\) 的 \(\text{LCP}\) 可以白嫖转移，就是自己转移自己，然后就是编辑操作依次考虑。
注意这里的操作都是在 T 串上的操作，对于 S 的操作，意义换一下式子也一样。\(\text{LCP}\) 可以通过二分 + 哈希来处理，时间复杂度 \(\mathcal{O}(nk^2\log n)\)，理论过不了，但是跑不满，SA 可以 \(\mathcal{O}(1)\) 处理 \(\text{LCP}\)，做到 \(\mathcal{O}(nk^2)\) 的正确复杂度，最后枚举 \(st\) 统计答案即可，没压行 QOJ 最短解。
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10,mod=998244353,inf=1e9,P=17771;
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
int K,n,m,f[35][70],ans[N];
ull hs[2][N],p[N];
char s[N],t[N];
inline int get(int l,int r,int id){return hs[id][r]-hs[id][l-1]*p[r-l+1];}
inline int LCP(int x,int y){
if(x<0||x>n||y<0||y>m)return 0;
int l=1,r=std::min(n-x+1,m-y+1),res=0;
while(l<=r){
int mid=l+r>>1;
if(get(x,x+mid-1,0)==get(y,y+mid-1,1))l=mid+1,res=mid;
else r=mid-1;
}return res;
}
signed main(){
// freopen("edit.in","r",stdin);freopen("edit.out","w",stdout);
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
std::cin>>K>>s+1>>t+1;n=strlen(s+1),m=strlen(t+1);
p[0]=1;for(int i=1;i<=std::max(n,m);++i)p[i]=p[i-1]*P;
for(int i=1;i<=n;++i)hs[0][i]=hs[0][i-1]*P+s[i]-'a'+1;
for(int i=1;i<=m;++i)hs[1][i]=hs[1][i-1]*P+t[i]-'a'+1;
for(int st=1;st<=m;++st){
for(int i=0;i<=K;++i)for(int j=0;j<=2*K;++j)f[i][j]=0;
f[0][K]=0;
for(int i=0;i<=K;++i)for(int j=-i;j<=i;++j){
f[i][j+K]+=LCP(f[i][j+K]+1,f[i][j+K]+st+j);
if(i!=K)
Max(f[i+1][j+K-1],std::min(f[i][j+K]+1,n)),
Max(f[i+1][j+K],std::min(f[i][j+K]+1,n)),
Max(f[i+1][j+K+1],f[i][j+K]);
}
for(int j=std::max(-K,1-n);j<=std::min(K,m-st-n+1);++j)
for(int i=0;i<=K;++i)if(f[i][j+K]>=n){ans[i]++;break;}
}for(int i=0;i<=K;++i)std::cout<<ans[i]<<'\n';
}