号家军集训 杂题选讲（CodeForces近几场）

讲师：冯施源

备注

已补完。

CF1456E

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1456/E

形式化题意：存在 个位数不超过 的二进制变量 ，其中 ，并给出 ，令函数 ：

$$f(x)=\sum_{i=0}^{k-1}\left(\left\lfloor\frac{x}{2^i}\right\rfloor\bmod 2\right)\cdot c_i$$

指定 的值，求 的最小值

数据范围：

简化贡献形式，记作：

$$f(x)=\sum_{i=0}^{+\infty}[x\operatorname{and}1]\cdot c_i$$

而从答案贡献来看，整个式子的计算是具有后效性的，所以考虑动态规划。考虑答案的贡献形式是位独立的，所以联想到数位 。

但容易发现，这个 并没有差分性质，所以对于上下界而言，我们都需要卡住。

在极高位时，，那这一部分的位是固定的，无法修改，而在第 位 ，这里的 是最大的，那么如果选 ，则 界被解除，否则 界被解除。当 界都被解除的时候，采取贪心策略就是保证了正确性的了。

但现在有 个区间都卡住了上下界，而如果我们当前挑选的某一位使得某一些限制不再卡界，我们可以将其视作被删除了，然后我们整一个类似于区间 的做法，设 表示这个区间内的限制都已经被删除了（不需要考虑）的贡献总和。

最后的状态是 表示当前在第 位，区间 之间的限制都已经被删除了， 位上下界的状态分别是 ， 位的状态分别是 。

如果这一位无法解除限制，则 。

否则枚举 区间分治，然后注意一下边界的特判就可以了。

AC Code

// ----- Eternally question-----
// Problem: E. XOR-ranges
// Contest: Codeforces - Codeforces Round 687 (Div. 1, based on Technocup 2021 Elimination Round 2)
// URL: https://codeforces.com/problemset/problem/1456/E
// Memory Limit:  256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-19 19:48:44
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=55;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,K;
ll L[MAXN],R[MAXN],C[MAXN];
ll Dp[MAXN][MAXN][MAXN][2][2][2][2];
ll Dfs(int c,int l,int r,bool l1,bool l2,bool r1,bool r2)
{
	if(c==K) return l>r?0:INF;
	ll &res=Dp[c][l][r][l1][l2][r1][r2];
	if(~res) return res;
	ll lt=((l1?R[l-1]:L[l-1])>>c)^l2;
	ll rt=((r1?R[r+1]:L[r+1])>>c)^r2;
	res=INF;
	checkMin(res,Dfs(c+1,l,r,l1,0,r1,0)+(l!=1&&r!=N?((lt&1)^(rt&1))*C[c]:0));
	for(int k=l;k<=r;++k)
		for(int t=0;t<=1;++t)
		{
			if(!c) checkMin(res,Dfs(c,l,k-1,l1,l2,t,0)+Dfs(c,k+1,r,t,0,r1,r2));
			ll v=(t?R[k]:L[k]);
			if(L[k]<=((v^(1ll<<c))&(~((1ll<<c)-1)))&&((v^(1ll<<c))|((1ll<<c)-1))<=R[k])
				checkMin(res,Dfs(c,l,k-1,l1,l2,t,1)+Dfs(c,k+1,r,t,1,r1,r2));
		}
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);
	for(int i=1;i<=N;++i) read(L[i],R[i]);
	for(int i=0;i<K;++i) read(C[i]);
	std::memset(Dp,-1,sizeof(Dp));
	write(Dfs(0,1,N,0,0,0,0));
	return 0;
}

---

CF1827E

题目简介

题目名称：

题目来源：

评测链接:https://codeforces.com/problemset/problem/1827/E

形式化题意：给定一棵有 个结点的树，其中存在 条路径，问是否存在一对点 无法通过两条路径相互到达。多测。

数据范围：

首先考虑 有没有什么有用的性质，很显然地，如果一条路径上存在某一点 能够到达 ，那这条路径上任意一点都可以到达 。

反过来想，如果两个点 无法到达，那么对于 ， 无法到达。

根据这两条性质，我们发现，只要保证叶结点两两能够互相到达，则整棵树就都可以互相到达。如果某个叶结点不存在路径，我们还需要考虑所有路径的端点。

设 表示 通过一条路径能够到达的深度最浅的结点。这个是好求的，可以用 解得。

考虑如果一个叶结点被包含在一条路径里，这个叶结点一定是这条路径的某一个端点。

对于叶结点对 ，如果 的 不是他们其中之一的话，则 一定会通过第三条路径才能连通，这样的话，就可以直接找到答案。至于这一步的实现，只需要判断深度最接近的两点即可，至于存在其他情况，我们另寻他法。

此时我们考虑换根，记深度最大的 为根 ，因为按照这样的话， 子树内所有 ，也就经过了 ，而对于不在 子树内的所有路径，就需要考虑其是否依然能够到达 ，此时重置 ，如果存在 ，说明存在一个原本 子树内的点和子树外的点无法互相到达，否则可以。

而对于上面那个判断深度接近的点对实际上是一个剪枝，不影响正确性，只是稍稍快那么一点。

最后时间复杂度 ，在于 和排序。多测记得清空，该清空的都得清空。否则就会浪费一上午（（（。

AC Code

// ----- Eternally question-----
// Problem: E. Bus Routes
// Contest: Codeforces - Codeforces Round 873 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1827/E
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// Written by: Eternity
// Time: 2023-07-23 08:23:02
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
int Test,N,M,Low[MAXN];
int Fa[MAXN],Dep[MAXN],Siz[MAXN],Son[MAXN];
std::vector<int>Edges[MAXN];
void dfsTree(int x,int last)
{
	Fa[x]=last,Dep[x]=Dep[last]+1,Siz[x]=1;
	for(int v:Edges[x])
	{
		if(v==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
}
int Top[MAXN];
void dfsChain(int x,int topf)
{
	Top[x]=topf;
	if(!Son[x]) return ;
	dfsChain(Son[x],topf);
	for(int v:Edges[x])
	{
		if(v==Fa[x]||v==Son[x]) continue;
		dfsChain(v,v);
	}
}
inline int getLca(int x,int y)
{
	while(Top[x]!=Top[y])
	{
		if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
		x=Fa[Top[x]];
	}
	return Dep[x]>Dep[y]?y:x;
}
std::vector<int>Rou[MAXN];
inline bool cmp(int a,int b){ return Dep[Low[a]]<Dep[Low[b]]; }
inline void solve()
{
	for(int i=1;i<=N;++i) Edges[i].clear(),Rou[i].clear(),Son[i]=0;
	read(N,M);
	for(int i=2,u,v;i<=N;++i) read(u,v),Edges[u].push_back(v),Edges[v].push_back(u);
	for(int i=1,u,v;i<=M;++i) read(u,v),Rou[u].push_back(v),Rou[v].push_back(u);
	dfsTree(1,0),dfsChain(1,1);
	std::vector<int>vec;
	for(int u=1;u<=N;++u)
	{
		Low[u]=u;
		if(Edges[u].size()>1) continue;
		vec.push_back(u);
		for(int v:Rou[u])
		{
			int lc=getLca(u,v);
			if(Dep[lc]<Dep[Low[u]]) Low[u]=lc;
		}
	}
	std::sort(vec.begin(),vec.end(),cmp);
	for(int i=0;i<(int)vec.size()-1;++i) if(getLca(Low[vec[i]],Low[vec[i+1]])!=Low[vec[i]])
		return write("NO\n",vec[i],' ',vec[i+1],'\n');
	int rt=Low[vec.back()];
	for(int x=1;x<=N;++x) Son[x]=0;
	dfsTree(rt,0),dfsChain(rt,rt);
	for(int u:vec)
	{
		int k=u;
		for(int v:Rou[u])
		{
			int lc=getLca(u,v);
			if(Dep[lc]<Dep[k]) k=lc;
		}
		if(k!=rt) return write("NO\n",u,' ',vec.back(),'\n');
	}
	puts("YES");
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--) solve();
	return 0;
}
/*

*/

---

CF1830E

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/contest/1830/problem/E

形式化题意：有一个长度为 的排列 ，定义一次操作为：

• 找到最大的 使得 ；
• 找到最小的 满足 ；
• 交换 。

一个排列的权值为将 变为升序排序需要操作的次数， 次询问单点修改，每次修改后求该排列的权值。

数据范围：

考虑从逆序对角度入手，发现升序的充要条件就是逆序对个数为 。

首先肯定不考虑修改，对于当前需要操作的 ，因为操作限制，所以区间 一定有 ，操作之后，这个区间的逆序对个数就会减少 。

注意到 ，如果 的话，则 ，之后一定存在一个 使得 ，如果 ，则 中一定存在 ，否则后段一定存在。所以 。

相对地，也有 。记录 为交换后的结果。

因此，，也就是 的减小量为 。

而升序序列的条件就是 与逆序对数为 。

操作个数就是前者的两倍减去后者。

前者可以线性维护，后者是动态逆序对，可以使用任意三位偏序算法维护，同样也可以使用主席树与树状数组套平衡树维护，时间复杂度 ，就是喜闻乐见的开空间了。

AC Code

// ----- Eternally question-----
// Problem: E. Bully Sort
// Contest: Codeforces - Codeforces Round 875 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1830/E
// Memory Limit: 1024 MB
// Time Limit: 10000 ms
// Written by: Eternity
// Time: 2023-07-23 10:28:35
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10,MAXM=5e4+10;
int N,Q;
std::mt19937 rnd(19260817);
namespace Pst
{
	#define ls(p) Tr[p].lc
	#define rs(p) Tr[p].rc
	struct PreSegment
	{ int lc,rc,val; }Tr[MAXN<<5];
	int Rt[MAXN],Idx=0;
	inline void pushUp(int p)
	{ Tr[p].val=Tr[ls(p)].val+Tr[rs(p)].val; }
	int build(int l,int r)
	{
		int x=++Idx;
		if(l==r) return x;
		int mid=(l+r)>>1;
		ls(x)=build(l,mid),rs(x)=build(mid+1,r);
		return x;
	}
	int querySum(int p1,int p2,int l,int r,int ql,int qr)
	{
		if(ql>qr||Tr[p1].val==Tr[p2].val) return 0;
		if(ql<=l&&r<=qr) return Tr[p2].val-Tr[p1].val;
		int mid=(l+r)>>1,res=0;
		if(ql<=mid) res+=querySum(ls(p1),ls(p2),l,mid,ql,qr);
		if(mid<qr) res+=querySum(rs(p1),rs(p2),mid+1,r,ql,qr);
		return res;
	}
	int modifyAdd(int p,int l,int r,int x)
	{
		int nd=++Idx;
		Tr[nd]=Tr[p];
		if(l==r) return ++Tr[nd].val,nd;
		int mid=(l+r)>>1;
		if(x<=mid) ls(nd)=modifyAdd(ls(p),l,mid,x);
		else rs(nd)=modifyAdd(rs(p),mid+1,r,x);
		return pushUp(nd),nd;
	}
	#undef ls
	#undef rs
};
namespace Tre
{
	struct Treap
	{ int chi[2],siz,val,rd,va1,sum; }Tr[MAXN<<4];
	int Idx;
	struct Fhq_Treap
	{
		int Rt,x,y,z;
		#define ls(p) Tr[p].chi[0]
		#define rs(p) Tr[p].chi[1]
		inline int newNode(int x,int y)
		{
			int id=++Idx;
			Tr[id].siz=1,Tr[id].val=x,Tr[id].rd=rnd();
			Tr[id].va1=Tr[id].sum=y;
			return id;
		}
		inline void upDate(int p)
		{
			Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1;
			Tr[p].sum=Tr[ls(p)].sum+Tr[rs(p)].sum+Tr[p].va1;
		}
		int merge(int u,int v)
		{
			if(!u||!v) return u^v;
			if(Tr[u].rd<Tr[v].rd)
			{
				rs(u)=merge(rs(u),v);
				return upDate(u),u;
			}
			else
			{
				ls(v)=merge(u,ls(v));
				return upDate(v),v;
			}
		}
		void split(int p,int k,int &u,int &v)
		{
			if(!p) u=v=0;
			else
			{
				if(Tr[p].val<=k) u=p,split(rs(p),k,rs(p),v);
				else v=p,split(ls(p),k,u,ls(p));
				upDate(p);
			}
			return ;
		}
		int getSum(int v)
		{
			x=y=0;
			split(Rt,v,x,y);
			int res=Tr[x].sum;
			Rt=merge(x,y);
			return res;
		}
		inline void insert(int v,int k)
		{
			x=y=z=0;
			split(Rt,v-1,x,y),split(y,v,y,z);
			if(!y) y=newNode(v,0);
			Tr[y].va1+=k,Tr[y].sum+=k;
			Rt=merge(merge(x,y),z);
		}
	}Bst[MAXN];
	inline int lowbit(int x){ return x&(-x); }
	inline int getLeq(int x,int v)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res+=Bst[x].getSum(v);
		return res;
	}
	inline int getLeq(int n,int l,int r,int k)
	{ return Pst::querySum(Pst::Rt[l-1],Pst::Rt[r],1,n,1,k)+(getLeq(r,k)-getLeq(l-1,k)); }
	inline void erase(int n,int x,int k)
	{ for(;x<=n;x+=lowbit(x)) Bst[x].insert(k,-1); }
	inline void insert(int n,int x,int k)
	{ for(;x<=n;x+=lowbit(x)) Bst[x].insert(k,1); }
};
int p[MAXN];
ll ans;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	Pst::Rt[0]=Pst::build(1,N);
	for(int i=1;i<=N;++i)
	{
		read(p[i]);
		ans+=std::max(p[i]-i,0)*2-Pst::querySum(Pst::Rt[0],Pst::Rt[i-1],1,N,p[i]+1,N);
		Pst::Rt[i]=Pst::modifyAdd(Pst::Rt[i-1],1,N,p[i]);
	}
	for(int x,y;Q--;)
	{
		read(x,y);
		int a=Tre::getLeq(N,x+1,y-1,p[x]);
		int b=Tre::getLeq(N,x+1,y-1,p[y]);
		ans-=(std::max(p[x]-x,0)+std::max(p[y]-y,0))*2-((a+(p[x]>p[y]?1:0))+(y-x-b-1));
		Tre::erase(N,x,p[x]),Tre::erase(N,y,p[y]);
		std::swap(p[x],p[y]);
		Tre::insert(N,x,p[x]),Tre::insert(N,y,p[y]);
		ans+=(std::max(p[x]-x,0)+std::max(p[y]-y,0))*2-((b+(p[x]>p[y]?1:0))+(y-x-a-1));
		write(ans,'\n');
	}
	return 0;
}
/*

*/

---

CF1835D

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1835/D

形式化题意：给定一个有 个点， 条边的有向图，求点对 满足 且存在一条从 到 的路径以及一条从 到 的路径长度 。

数据范围：

考虑一个不同寻常的 ，那是这些点对一定位于同一个 里，所以考虑缩点后在一个 里单独做。考虑把这个 里所有环找出来，设 ，所以，如果两个点互相到达，应当存在一种 的求解方法使得 ，至于 的构造，可以证明其充分必要性，所以随意找出 中的一棵生成树后以其 记作 。

发现仅有满足 或者 时存在合法解，然后求解上述条件下所有 的对数就行了，注意这里的 有交换律。

AC Code

// ----- Eternally question-----
// Problem: Doctor's Brown Hypothesis
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1835D
// Memory Limit:  250 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-18 21:21:32
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXM=2e5+10;
int N,M;
ll K,ans;
struct G
{ int next,to; }Edge[MAXM<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Dfn[MAXN],Low[MAXN],Stk[MAXN],Top,Cnt;
bool Ins[MAXN],Vis[MAXN];
int Scc[MAXN],Sc;
std::vector<int>vec[MAXN];
int Fa[MAXN],Dep[MAXN],Buc[MAXN],d;
void Tarjan(int x)
{
	Dfn[x]=Low[x]=++Cnt,Stk[++Top]=x,Ins[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if(!Dfn[(v=Edge[e].to)])
		{
			Tarjan(v);
			checkMin(Low[x],Low[v]);
		}
		else if(Ins[v]) checkMin(Low[x],Dfn[v]);
	}
	if(Dfn[x]==Low[x])
	{
		Scc[x]=++Sc;
		while(Stk[Top]!=x)
		{
			Scc[Stk[Top]]=Sc;
			vec[Sc].emplace_back(Stk[Top]);
			Ins[Stk[Top]]=0,--Top;
		}
		Ins[x]=0,--Top;
		vec[Sc].emplace_back(x);
	}
}
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
void dfsTree(int x,int last,int cur)
{
	Vis[x]=1,Fa[x]=last,Dep[x]=Dep[last]+1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if(Scc[(v=Edge[e].to)]!=cur) continue;
		if(!Vis[v]) dfsTree(v,x,cur);
		else d=gcd(d,std::abs(Dep[v]-Dep[x]-1));
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,K);
	for(int i=1,u,v;i<=M;++i) read(u,v),addEdge(u,v);
	for(int x=1;x<=N;++x) if(!Dfn[x]) Tarjan(x);
	for(int i=1;i<=Sc;++i)
	{
		int max_dep=0;d=0;
		dfsTree(vec[i][0],0,i);
		for(int v:vec[i]) ++Buc[Dep[v]],checkMax(max_dep,Dep[v]);
		if(d!=0)
		{
			if(K%d==0)
			{
				for(int j=1;j<=max_dep;++j)
				{
					ans+=(ll)Buc[j]*(Buc[j]+1)/2;
					if(j>d) ans+=(ll)Buc[j]*Buc[j-d],Buc[j]+=Buc[j-d];
				}	
			}
			else if(d%2==0&&K%d==d/2)
			{
				for(int j=d/2+1;j<=max_dep;++j)
				{
					ans+=(ll)Buc[j]*Buc[j-d/2];
					if(j>d) Buc[j]+=Buc[j-d];
				}
			}
		}
		for(int j=1;j<=max_dep;++j) Buc[j]=0;
	}
	write(ans);
	return 0;
}

---

CF1835E

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1835/E

形式化题意：给定一个长度为 ，字符集为 的字符串，你有一个有 个按键的键盘（字符集加上一个退格键，即删除），初始你并不知道每个按键对应什么，但当你按下一个按键后你就马上可以知道按键的对应。求按出对应字符串的期望步数，对 取模。

数据范围：

考虑步数上界，就是先按出 个按键，然后全部删除并按出对应字符串，至多需要 步，是步数上界。但显然不是答案。

考虑分类讨论：

• 当前已经知道了 backspace 键：
  • 下一个字母对应的键我们已经知道了，则直接按。
  • 下一个字母对应的键我们并不知道，那就瞎按不知道的，每次按了之后退格直到上一种情况。
• 当前并不知道 backspace 键：
  • 当前按出的字符串是目标字符串前缀：
    • 如果下一个字母对应的键我们已经知道，则按；
    • 如果下一个字母对应的键我们不知道，则瞎按不知道的。
  • 如果按出的字符串不是目标字符串的前缀，那瞎按。

只考虑每个字符第一次出现的时候才会产生期望步数，所以我们按照每一个字符出现的顺序进行递推。

设 表示当前已经输入完成了前 个字符，且有 个键知道，但并没有输入。

• 当 时，当前不知道 backspace 的键位，且当前串是目标串的前缀。
• 当 时，当前不知道 backspace 的键位，当前串不是目标串的前缀。
• 当 时，知道 backspace 的键位，并不确定知不知道下一个字符的键位。
• 当 时，知道 backspace 的键位，确定不知道下一个字符的键位。

用 表示第 种字符第一次出现的位置。

s=1的转移

这种情况下，前面的字符都没有挂，此时 恒成立，但对于下一位，如果知道则直接转移，否则只能瞎按。

$$f_{i,0,1}\longleftarrow \begin{cases} \displaystyle\frac{1}{m-i+1}(f_{i+1,0,1}+p_{i+1}-p_i)\\\\ \displaystyle\frac{1}{m-i+1}(f_{i+1,0,3}+1+[i\neq 0])\\\\ \displaystyle\frac{m-i-1}{m-i+1}(f_{i,1,2}+2) \end{cases}$$

三种情况分别是，按键正确，按键到 backspace，按键错误的情况。

s=2的转移

在不知道是啥的里面瞎按即可。

$$f_{i,j,2}\longleftarrow \begin{cases} \displaystyle\frac{m-i-j}{m-i-j+1}(f_{i,j+1,2}+2)\\\\ \displaystyle\frac{1}{m-i-j+1}\cdot\frac{j-1}{m-i-1}f_{i+1,j-1,3}\\\\ \displaystyle\frac{1}{m-i-j+1}\cdot\frac{m-j}{m-i-1}f_{i+1,j,4} \end{cases}$$

三种情况分别是，没按到 backspace，还按错了；按对了；按错了，但是又知道了一个。

至于按倒了 backspace 的贡献，我们将其与第一种情况合并，计算出了删除多余字符串的贡献了。

s=3的转移

相比 而言，少了按到 backspace 的可能，其余一致。

$$f_{i,j,3}\longleftarrow \begin{cases} \displaystyle\frac{j}{m-i}(f_{i+1,j-1,3}+p_{i+1}-p_{i})\\\\ \displaystyle\frac{m-i-j}{m-i}f_{i,j,4} \end{cases}$$

s=4的转移

抉择是在不知道的 个中瞎按一个。

$$f_{i,j,4}\longleftarrow \begin{cases} \displaystyle\frac{1}{m-i-j}(f_{i+1,j,3}+l_{i+1}-l_i)\\\\ \displaystyle\frac{m-i-j-1}{m-i-j}(f_{i,j+1,4}+2) \end{cases}$$

就是按错和没按错。

然后对于所有的 ，其中 表示 中包含的字符集，答案为 ，时空复杂度 。

AC Code

// ----- Eternally question-----
// Problem: E. Old Mobile
// Contest: Codeforces - Codeforces Round 880 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1835/E
// Memory Limit:  256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-18 15:28:19
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10,MAXM=1e3+10;
const int Mod=1e9+7;
int N,M,a[MAXN];
int Pre[MAXM],Vis[MAXN],Cnt;
ll Dp[MAXM][MAXM][5],Inv[MAXM];
inline ll qPow(ll a,ll b)
{
	ll res=1;
	for(;b;b>>=1,a=a*a%Mod) (b&1)&&(res=res*a%Mod);
	return res;
}
inline void add(ll &x,ll y){ x=x+y>=Mod?x+y-Mod:x+y; }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M),Inv[1]=1;
	for(int i=1,x;i<=N;++i)
	{
		read(x);
		if(!Vis[x]) Pre[Cnt]=i-1,Vis[x]=++Cnt;
		a[i]=Vis[x];
	}
	Pre[Cnt]=N;
	for(int i=2;i<=M+1;++i) Inv[i]=(Mod-Mod/i)*Inv[Mod%i]%Mod;
	for(int i=Cnt-1;~i;--i)
		for(int j=M-i;~j;--j)
		{
			if(M-i-j)
			{
				add(Dp[i][j][4],(Dp[i+1][j][3]+Pre[i+1]-Pre[i])*Inv[M-i-j]%Mod),
				add(Dp[i][j][4],(Dp[i][j+1][4]+2)*Inv[M-i-j]%Mod*(M-i-j-1)%Mod);
			}
			if(j) add(Dp[i][j][3],(Dp[i+1][j-1][3]+Pre[i+1]-Pre[i])*Inv[M-i]%Mod*j%Mod);
			add(Dp[i][j][3],Dp[i][j][4]*(M-i-j)%Mod*Inv[M-i]%Mod);
			add(Dp[i][j][2],Dp[i][j][4]*(M-i-j)%Mod*Inv[M-i-1]%Mod*Inv[M-i-j+1]%Mod);
			if(j) add(Dp[i][j][2],(Dp[i+1][j-1][3]+Pre[i+1]-Pre[i])*(j-1)%Mod*Inv[M-i-1]%Mod*Inv[M-i-j+1]%Mod);
			add(Dp[i][j][2],(Dp[i][j+1][2]+2)*(M-i-j)%Mod*Inv[M-i-j+1]%Mod);
			if(!j)
			{
				add(Dp[i][0][1],(Dp[i+1][0][1]+Pre[i+1]-Pre[i])%Mod*Inv[M-i+1]%Mod);
				add(Dp[i][0][1],(Dp[i][0][3]+1+(i!=0))*Inv[M-i+1]%Mod);
				add(Dp[i][0][1],(Dp[i][1][2]+2)*(M-i-1)%Mod*Inv[M-i+1]%Mod);
			}
		}
	write(Dp[0][0][1]);
	return 0;
}

---

CF1844G

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1844/G

形式化题意：给定一个有 个结点的树，现在给出所有 表示 的距离，尝试还原出这棵树的边权。

数据范围：

考虑贡献方式：，这里我们记 表示 到根结点的边权和。

首先有 ，考虑通过这个与上述式子进行递推，但这样是无法处理的，我们考虑另外一种形式：

在 条件下，关于 的限制无用，可以直接得到 ，然后我们就得到了所有 条件下的 ，据此，我们还可以推出 下的 ，也就是 ，然后按照倍增的思路，因为 ，所以 不会很大，到大概 差不多就是真实值了。

AC Code

// ----- Eternally question-----
// Problem: G. Tree Weights
// Contest: Codeforces - Codeforces Round  884 (Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/1844/G
// Memory Limit:  256 MB
// Time Limit: 5000 ms
// Written by: Eternity
// Time: 2023-07-19 14:35:33
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
const int MAXN=1e5+10,MAXS=20;
int N,Dep[MAXN],Rt[MAXN][MAXS];
ll Dist[MAXN],V[MAXN],Lca[MAXN],Val[MAXN];
int Dfn[MAXN],Eid[MAXN],Cnt;
std::vector<Pir>Edges[MAXN];
void dfsTree(int x,int last)
{
	Dep[x]=Dep[last]+1;
	Rt[Dfn[x]=++Cnt][0]=last;
	for(auto v:Edges[x]) if(v.fir!=last) dfsTree(v.fir,x),Eid[v.fir]=v.sec;
}
inline int get(int x,int y){ return Dep[x]>Dep[y]?y:x; }
inline int getLca(int x,int y)
{
	if(x==y) return x;
	if((x=Dfn[x])>(y=Dfn[y])) std::swap(x,y);
	int d=std::__lg(y-x++);
	return get(Rt[x][d],Rt[y-(1<<d)+1][d]);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1,u,v;i<N;++i)
	{
		read(u,v);
		Edges[u].emplace_back(v,i);
		Edges[v].emplace_back(u,i);
	}
	dfsTree(1,0);
	for(int i=1;i<N;++i) read(Dist[i]);
	for(int s=1;(1<<s)<=N;++s)
		for(int i=1;i+(1<<s)-1<=N;++i)
			Rt[i][s]=get(Rt[i][s-1],Rt[i+(1<<(s-1))][s-1]);
	for(int i=1;i<N;++i) Lca[i]=getLca(i,i+1);
	for(int s=0;s<60;++s)
	{
		ll u=(1ll<<s)-1;
		for(int i=1;i<N;++i)
		{
			ll r=(Dist[i]&u)+(V[Lca[i]]<<1);
			V[i+1]=(r+u+1-V[i])&u;
		}
	}
	for(int i=2;i<=N;++i)
	{
		int fa=Rt[Dfn[i]][0];
		if(V[i]<=V[fa]) return puts("-1"),0;
		Val[Eid[i]]=V[i]-V[fa];
	}
	for(int i=1;i<N;++i)
	{
		ll dis=V[i]+V[i+1]-2*V[Lca[i]];
		if(dis!=Dist[i]) return puts("-1"),0;
	}
	for(int i=1;i<N;++i) write(Val[i],'\n');
	return 0;
}

---