https://oj.gxyzh.com/d/hzoj/contest/699fbd72c524e405961f848c
这场比赛不太难，\(A\) 了两道。
两棵树
题解
由于联通块不方便计数，考虑转化。
发现 联通块个数=剩余点数-剩余边数
所以 \(X\times Y=(T_{点}-T_{边})(U_{点}-U_{边})=T_{点}U_{点}-T_{点}U_{边}-T_{边}U_{点}+T_{边}U_{边}\)
分类讨论：
- \(点 \times 点\) 每个点存在概率为 \(\frac{1}{2}\)，相同的两个点存在概率为 \(0\)，期望为 \(\frac{n(n-1)}{4}\)。
- \(点 \times 边\) 每条边存在概率为 \(\frac{1}{4}\)，当 边的顶点编号 与 点编号 相同时概率为 \(0\)，期望为 \(\frac{(n-1)(n-2)}{8}\)。
- \(边 \times 边\) 每对边存在概率为 \(\frac{1}{16}\)，当 边的顶点编号 存在相同时概率为 \(0\)。
此情况不能直接计算，需要枚举每条边计算产生的贡献，设边为 \((x,y)\) 与 \((u,v)\)。
用 \(n-1\) 减去与 \(x,y\) 重合的点 \(u,v\)，若 \((x,y)=(u,v)\)，则需要加回来，用 \(set\) 维护。
时间复杂度 \(O(nlogn)\)。
代码
#include<iostream>
#include<set>
#define int long long
using namespace std;
constexpr int N=2e5+5,p=998244353;
int n,m,ans,mul[5]={0,499122177,748683265,873463809,935854081};
struct E{ int u,v; }T[N];
set<int> s[N];
signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<n;i++)cin>>T[i].u>>T[i].v;for(int i=1,u,v;i<n;i++)cin>>u>>v,s[u].insert(v),s[v].insert(u);ans=(n*(n-1)%p*mul[2]%p-(n-1)*(n-2)%p*mul[2]%p)%p;for(int i=1,u,v;i<n;i++){u=T[i].u,v=T[i].v;int cnt=n-1-s[u].size()-s[v].size();auto it=lower_bound(s[u].begin(),s[u].end(),v);cnt+=((*it)==v);ans=(ans+cnt*mul[4]%p)%p;}cout<<(ans+p)%p<<'\n';return 0;
}
编辑
题解
对于 \(60pts\)，可以看 这道题。
对于 \(100pts\)。
注意到题目对 \(dp\) 值域进行限制，且上面 \(O(n^3)\) 的 \(dp\) 有许多相同的值 ，考虑将 值域 和 下标 转换（这种思想在数据结构中比较常用，\(dp\) 中比较难用）。
不妨将区间分组处理，先计算 \(T\) 的前缀。
设 \(dp_{i,j}\)，表示 \(i\) 次修改，可以使得 \(S[1,\dots,dp_{i,j}]\) 可以转换为 \(T[1,\dots,dp_{i,j}+j]\)，并且保证\(dp_{i,j}\) 最大，这里不难发现 \(j\in[-k,k]\)。
转移考虑刷表，\(dp_{i,j}\gets dp_{i,j}+LCP(S[dp_{i,j}+1,\dots,n],T[dp_{i,j}+j+1,\dots,m])\)。
然后再对 \(dp_{i+1,j},dp_{i+1,j-1},dp_{i+1,j+1}\) 转移。
这样可以 \(O(k^2)\) 得到 \(dp\)，然后对于 \(dp_{i,j}=n\) 统计 \(ans\)。
考虑对 \(T\) 每个后缀都这样处理，计算 \(LCP\) 使用 \(hash\) + 二分。
时间复杂度 \(O(nk^2logn)\)。
代码
#include<iostream>
#include<string.h>
#define ull unsigned long long
using namespace std;
constexpr int N=5e4+5,M=35,p=131;
int K,ans[M],n,m,dp[M][M<<1];
char s[N],t[N];
ull hash1[N],hash2[N],pow[N]={1};
int flag[N];
int LCP(int x,int y){if(x>n||y>m||!x||!y)return 0;x--,y--; int L=-1,R=min(n-x,m-y)+1,mid;while(L+1<R){mid=(L+R)>>1;ull has1=hash1[x+mid]-hash1[x]*pow[mid];ull has2=hash2[y+mid]-hash2[y]*pow[mid];if(has1==has2)L=mid;else R=mid;}return L;
}void Solve(int id){for(int i=0;i<=K;i++)for(int j=-i;j<=i;j++){dp[i][j+K]=min(dp[i][j+K],n);dp[i][j+K]+=LCP(dp[i][j+K]+1,dp[i][j+K]+1+j+id);if(dp[i][j+K]==-1)continue;if(j-1+K>=0)dp[i+1][j-1+K]=max(dp[i+1][j-1+K],dp[i][j+K]+1);//删除末尾元素 dp[i+1][j+K]=max(dp[i+1][j+K],dp[i][j+K]+1);//修改末尾元素dp[i+1][j+1+K]=max(dp[i+1][j+1+K],dp[i][j+K]);//增添末尾元素 }for(int j=-K;j<=K;j++)flag[n+j]=1e9;for(int i=0;i<=K;i++)for(int j=-K;j<=K;j++)if(dp[i][j+K]==n&&0<n+j&&n+j<=m-id)flag[n+j]=min(flag[n+j],i);for(int j=-K;j<=K;j++)if(flag[n+j]!=1e9)ans[flag[n+j]]++;
}signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>K>>(s+1)>>(t+1);n=strlen(s+1),m=strlen(t+1);for(int i=1;i<=5e4;i++)pow[i]=pow[i-1]*p;for(int i=1;i<=n;i++)hash1[i]=hash1[i-1]*p+s[i];for(int i=1;i<=m;i++)hash2[i]=hash2[i-1]*p+t[i];for(int L=1;L<=m;L++){for(int i=0;i<=K;i++)for(int j=-K;j<=K;j++)dp[i][j+K]=-1;dp[0][K]=LCP(1,L);Solve(L-1);}for(int i=0;i<=K;i++)cout<<ans[i]<<'\n';return 0;
}