杂题选做 - 苏子佩のBlog

凌乱平衡树

给定两棵 $Treap$ ，每次将某棵树上的某个点 $rotate$ ，然后将两棵树合并，询问每次合并后所有点的深度和。

首先深度和显然可以先一遍 $dfs$ 处理出来，然后计算两棵树原来的深度和，之后在合并的时候计算额外的贡献即可。

在合并的时候只有左侧树的右链和右侧树的左链有用，所以只需要维护这两个链即可，那么本质上是序列的问题，考虑一次合并的时候，如果当前左侧点对应的子树大小为 $siz_1$ ，右侧子树大小为 $siz_2$ ，那么如果将左侧子树作为根，那么答案加上 $siz_2$ 否则答案加上 $siz_1$ ，所以只需要考虑当前点贡献多少次即可，不难发现贡献是一个区间的形式，所以直接用线段树维护。

注意几点:

旋转时记得修改原来树的贡献
修改关键链上的点对应线段树的权值
修改贡献后记得考虑下一个点的修改
极大值要设置的大一些

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=2e5+10;
ll res;
struct Treap{
	int n,rt,ch[N][2],fa[N],siz[N];
	void dfs(rint u){
		if(!u)return ;
		dfs(ch[u][0]);
		dfs(ch[u][1]);
		siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;
	}
	void init(){
		for(rint i=1;i<=n;i++){
			scanf("%d%d",&ch[i][0],&ch[i][1]);
			fa[ch[i][0]]=fa[ch[i][1]]=i;
		}
		rt=1;
		while(fa[rt])rt=fa[rt];
		dfs(rt);
		for(rint i=1;i<=n;i++)
			res+=siz[i];
	}
}t1,t2;
set<int> s1,s2;
int val1[N<<2],val2[N<<2];
void update1(rint rt,rint l,rint r,rint pos,rint v){
	val1[rt]+=v;
	if(l==r)return ;
	rint mid=l+r>>1;
	if(pos<=mid)update1(rt<<1,l,mid,pos,v);
	else update1(rt<<1|1,mid+1,r,pos,v);
}
void update2(rint rt,rint l,rint r,rint pos,rint v){
	val2[rt]+=v;
	if(l==r)return ;
	rint mid=l+r>>1;
	if(pos<=mid)update2(rt<<1,l,mid,pos,v);
	else update2(rt<<1|1,mid+1,r,pos,v);
}
ll query1(rint rt,rint l,rint r,rint cl,rint cr){
	if(!val1[rt])return 0;
	if(cl<=l&&r<=cr)return val1[rt];
	rint mid=l+r>>1;
	rll res=0;
	if(cl<=mid)res+=query1(rt<<1,l,mid,cl,cr);
	if(cr>mid)res+=query1(rt<<1|1,mid+1,r,cl,cr);
	return res;
}
ll query2(rint rt,rint l,rint r,rint cl,rint cr){
	if(!val2[rt])return 0;
	if(cl<=l&&r<=cr)return val2[rt];
	rint mid=l+r>>1;
	rll res=0;
	if(cl<=mid)res+=query2(rt<<1,l,mid,cl,cr);
	if(cr>mid)res+=query2(rt<<1|1,mid+1,r,cl,cr);
	return res;
}
bool vis1[N],vis2[N];
void rotate1(rint x){
	rint y=t1.fa[x];rint z=t1.fa[y];
	res-=t1.siz[y];res-=t1.siz[x];
	if(vis1[y]){
		update1(1,1,t1.n,t1.siz[y],-1);
		rll val=query2(1,1,t2.n,t1.siz[y]+1,*s1.upper_bound(t1.siz[y]));
		res-=t1.siz[y]*val;
		res+=(*--s1.find(t1.siz[y]))*val;
		res-=*--s2.upper_bound(t1.siz[y]);
		s1.erase(t1.siz[y]);
		if(vis1[x]){
			update1(1,1,t1.n,t1.siz[x],-1);
			val=query2(1,1,t2.n,t1.siz[x]+1,*s1.upper_bound(t1.siz[x]));
			res-=t1.siz[x]*val;
			res+=(*--s1.find(t1.siz[x]))*val;
			res-=*--s2.upper_bound(t1.siz[x]);
			s1.erase(t1.siz[x]);
		}
	}
	rint k=t1.ch[y][1]==x;
	t1.ch[z][t1.ch[z][1]==y]=x;t1.fa[x]=z;
	t1.ch[y][k]=t1.ch[x][!k];t1.fa[t1.ch[x][!k]]=y;
	t1.ch[x][!k]=y;t1.fa[y]=x;
	t1.siz[y]=t1.siz[t1.ch[y][0]]+t1.siz[t1.ch[y][1]]+1;
	t1.siz[x]=t1.siz[t1.ch[x][0]]+t1.siz[t1.ch[x][1]]+1;
	if(vis1[y]){
		update1(1,1,t1.n,t1.siz[x],1);
		if(vis1[x]){
			s1.insert(t1.siz[x]);
			vis1[y]=0;
			rll val=query2(1,1,t2.n,t1.siz[x]+1,*s1.upper_bound(t1.siz[x]));
			res+=t1.siz[x]*val;
			res-=(*--s1.find(t1.siz[x]))*val;
			res+=*--s2.upper_bound(t1.siz[x]);
		}else {
			s1.insert(t1.siz[y]);
			rll val=query2(1,1,t2.n,t1.siz[y]+1,*s1.upper_bound(t1.siz[y]));
			res+=t1.siz[y]*val;
			res-=(*--s1.find(t1.siz[y]))*val;
			res+=*--s2.upper_bound(t1.siz[y]);
			s1.insert(t1.siz[x]);
			val=query2(1,1,t2.n,t1.siz[x]+1,*s1.upper_bound(t1.siz[x]));
			res+=t1.siz[x]*val;
			res-=(*--s1.find(t1.siz[x]))*val;
			res+=*--s2.upper_bound(t1.siz[x]);
			vis1[x]=1;
			update1(1,1,t1.n,t1.siz[y],1);
		}
	}
	res+=t1.siz[y];res+=t1.siz[x];
}
void rotate2(rint x){
	rint y=t2.fa[x];rint z=t2.fa[y];
	res-=t2.siz[y];res-=t2.siz[x];
	if(vis2[y]){
		update2(1,1,t2.n,t2.siz[y],-1);
		rll val=query1(1,1,t1.n,t2.siz[y],*s2.upper_bound(t2.siz[y])-1);
		res-=t2.siz[y]*val;
		res+=(*--s2.find(t2.siz[y]))*val;
		res-=*--s1.lower_bound(t2.siz[y]);
		s2.erase(t2.siz[y]);
		if(vis2[x]){
			update2(1,1,t2.n,t2.siz[x],-1);
			val=query1(1,1,t1.n,t2.siz[x],*s2.upper_bound(t2.siz[x])-1);
			res-=t2.siz[x]*val;
			res+=(*--s2.find(t2.siz[x]))*val;
			res-=*--s1.lower_bound(t2.siz[x]);
			s2.erase(t2.siz[x]);
		}
	}
	rint k=t2.ch[y][1]==x;
	t2.ch[z][t2.ch[z][1]==y]=x;t2.fa[x]=z;
	t2.ch[y][k]=t2.ch[x][!k];t2.fa[t2.ch[x][!k]]=y;
	t2.ch[x][!k]=y;t2.fa[y]=x;
	t2.siz[y]=t2.siz[t2.ch[y][0]]+t2.siz[t2.ch[y][1]]+1;
	t2.siz[x]=t2.siz[t2.ch[x][0]]+t2.siz[t2.ch[x][1]]+1;
	if(vis2[y]){
		update2(1,1,t2.n,t2.siz[x],1);
		if(vis2[x]){
			s2.insert(t2.siz[x]);
			vis2[y]=0;
			rll val=query1(1,1,t1.n,t2.siz[x],*s2.upper_bound(t2.siz[x])-1);
			res+=t2.siz[x]*val;
			res-=(*--s2.find(t2.siz[x]))*val;
			res+=*--s1.lower_bound(t2.siz[x]);
		}else {
			update2(1,1,t2.n,t2.siz[y],1);
			s2.insert(t2.siz[y]);
			rll val=query1(1,1,t1.n,t2.siz[y],*s2.upper_bound(t2.siz[y])-1);
			res+=t2.siz[y]*val;
			res-=(*--s2.find(t2.siz[y]))*val;
			res+=*--s1.lower_bound(t2.siz[y]);
			s2.insert(t2.siz[x]);
			val=query1(1,1,t1.n,t2.siz[x],*s2.upper_bound(t2.siz[x])-1);
			res+=t2.siz[x]*val;
			res-=(*--s2.find(t2.siz[x]))*val;
			res+=*--s1.lower_bound(t2.siz[x]);
			vis2[x]=1;
		}
	}
	res+=t2.siz[y];res+=t2.siz[x];
}
int main(){
	scanf("%d%d",&t1.n,&t2.n);
	t1.init();t2.init();
	s1.insert(0);s2.insert(0);
	s1.insert(2e5+2);s2.insert(2e5+2);
	for(rint x=t1.rt;x;x=t1.ch[x][1])
		s1.insert(t1.siz[x]),update1(1,1,t1.n,t1.siz[x],1),vis1[x]=1;
	for(rint x=t2.rt;x;x=t2.ch[x][0])
		s2.insert(t2.siz[x]),update2(1,1,t2.n,t2.siz[x],1),vis2[x]=1;
	rint lst=0;
	for(set<int>::reverse_iterator it=s1.rbegin();it!=s1.rend();it++){
		rint v=*it;
		if(lst&&v)
			res+=1ll*v*query2(1,1,t2.n,v+1,lst);
		lst=v;
	}
	lst=0;
	for(set<int>::reverse_iterator it=s2.rbegin();it!=s2.rend();it++){
		rint v=*it;
		if(lst&&v)
			res+=1ll*v*query1(1,1,t1.n,v,lst-1);
		lst=v;
	}
	printf("%lld\n",res);
	rint q;
	scanf("%d",&q);
	while(q--){
		rint op,x;
		scanf("%d%d",&op,&x);
		if(op==1)rotate1(x);
		else rotate2(x);
		printf("%lld\n",res);
	}
	return 0;
}

西克

给定一棵树，树上每个点有两个权值， $a,b$ 表示如果走到这个点，手里拿的球是 $a$ ，那么手中的球会变成 $b$ ，询问从 $x$ 到 $y$ ，手中拿着的球是 $b_x$ ，到达 $y$ 时手里拿的球是什么。

考虑将路径分成两部分，一部分是从 $x$ 到 $lca$ ，另一部分是从 $lca$ 到 $y$ ，前半部分可以直接用倍增的做法，考虑后半部分怎么做，发现没有办法向下走，主要原因是向下走的路径太多，没办法维护，注意到从 $y$ 到 $lca$ 的路径可以被分成不超过 $\log$ 段重链，所以可以对于每一段重链预处理一下，然后倍增跳即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
char buf[1<<20],*p1,*p2;
inline char gc(){return p1==p2?p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2?EOF:*p1++:*p1++;}
inline int read(){
	rint x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
	return x;
}
const int N=2e6+10;
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx;
void Ins(rint a,rint b){e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;}
unsigned int S1,S2;
unsigned int rnd(){
	S1*=S2,S2>>=S1&13,S2-=S1,S1^=S2;
	return ((S1-S2)&(S1+S2))^(S1*S2>>4);
}
int a[N],b[N],p[N][23],fa[N],d[N],lst[N],siz[N],son[N],dfn[N],Time,rk[N],tp[N];
void dfs1(rint u){
	p[u][0]=lst[b[u]];
	rint t=lst[a[u]];
	lst[a[u]]=u;
	siz[u]=1;
	for(rint i=0;p[u][i];i++)
		p[u][i+1]=p[p[u][i]][i];
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa[u])continue;
		fa[v]=u;
		d[v]=d[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])
			son[u]=v;
	}
	lst[a[u]]=t;
}
void dfs2(rint u,rint t){
	tp[u]=t;dfn[u]=++Time;rk[Time]=u;
	if(son[u])
		dfs2(son[u],t);
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
vector<int> vec[N];
int nxt[N][22],stk[N],top;
inline int getlca(rint x,rint y){
	top=0;stk[++top]=y;
	while(tp[x]!=tp[y]){
		if(d[tp[x]]>d[tp[y]]){
			x=fa[tp[x]];
		}else {
			y=fa[tp[y]];
			stk[++top]=y;
		}
	}
	return d[x]>d[y]?y:x;
}
vector<int>::iterator it;
inline int getnxt(rint x,rint l,rint r){
	it=lower_bound(vec[x].begin(),vec[x].end(),l);
	if(it==vec[x].end())return -1;
	if(*it>r)return -1;
	return rk[*it];
}
int main(){
	rint n=read(),q=read();
	S1=read(),S2=read();
	if(n<=5e5){
		for(rint i=1;i<=n;i++)
			a[i]=read(),b[i]=read();
	}else {
		for(rint i=1;i<=5e5;i++)
			a[i]=read(),b[i]=read();
		for(rint i=500001;i<=n;i++){
			a[i]=rnd()%n+1;b[i]=a[rnd()%500000+1];
			if(a[i]==b[i]){
				++a[i];
				if(a[i]>n)a[i]=1;
			}
		}
	}
	for(rint i=2;i<=n;i++){
		rint x=read();
		Ins(x,i);
	}
	dfs1(1);
	dfs2(1,1);
	for(rint i=1;i<=n;i++)
		vec[a[rk[i]]].push_back(i);
	for(rint i=1;i<=n;i++){
		if(tp[i]==i){
			rint cr=dfn[i];
			while(tp[rk[cr+1]]==i)cr++;
			for(rint j=cr;j>=dfn[i];j--){
				rint x=rk[j];
				nxt[x][0]=lst[b[x]];
				for(rint k=0;nxt[x][k];k++)
					nxt[x][k+1]=nxt[nxt[x][k]][k];
				lst[a[x]]=x;
			}
			for(rint j=dfn[i];j<=cr;j++)
				lst[a[rk[j]]]=0;
		}
	}
	rint res=0;
	while(q--){
		rint x=read(),y=read();
		rint lc=getlca(x,y);
		rint now=x;
		for(rint i=20;~i;i--)
			if(p[now][i]&&d[p[now][i]]>=d[lc])
				now=p[now][i];
		now=b[now];
		rint pos=lc;
		for(rint i=top;i;i--){
			rint t=getnxt(now,dfn[pos],dfn[stk[i]]);
			if(t!=-1){
				for(rint j=20;~j;j--)
					while(nxt[t][j]&&dfn[nxt[t][j]]<=dfn[stk[i]])
						t=nxt[t][j];
				now=b[t];
			}
			pos=tp[stk[i-1]];
		}
		res^=now;
	}
	printf("%d\n",res);
	return 0;
}

苯为

有一棵树，复制 $A$ 份形成一个森林，枚举一个二元组 $(s,t)$ ，然后对于相邻的两棵树链接 $s$ 和 $t$ ，之后用 $k$ 种颜色给形成的基环树进行染色，问染色的方案。

不难发现最终的答案只和环的大小有关系，除了环以外别的点的贡献都是 $k-1$ ，所以只需要对于每个环进行处理即可，用换根 $dp$ 。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=1e6+10;
const int p=421969921;
inline int read(){
	rint x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
	return x;
}
inline int Add(rint x,rint y){x+=y;return x>=p?x-p:x;}
inline int Del(rint x,rint y){x-=y;return x>=0?x:x+p;}
ll fpow(rll a,rll b){
	rll res=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)res=res*a%p;
	return res;
}
struct Mat{
	int x[2][2];
	Mat operator * (const Mat&A)const{
		Mat res;
		for(rint i=0;i<2;i++){
			for(rint j=0;j<2;j++){
				rll tmp=0;
				for(rint k=0;k<2;k++)
					tmp+=1ll*x[i][k]*A.x[k][j]%p;
				res.x[i][j]=tmp%p;
			}
		}
		return res;
	}
	Mat operator + (const Mat&A)const{
		Mat res;
		for(rint i=0;i<2;i++)
			for(rint j=0;j<2;j++)
				res.x[i][j]=Add(x[i][j],A.x[i][j]);
		return res;
	}
	Mat operator - (const Mat&A)const{
		Mat res;
		for(rint i=0;i<2;i++)
			for(rint j=0;j<2;j++)
				res.x[i][j]=Del(x[i][j],A.x[i][j]);
		return res;
	}
	Mat operator ^ (const ll&A)const{
		Mat res,a=*this;
		rll k=A;
		res.x[0][0]=res.x[1][1]=1;
		res.x[1][0]=res.x[0][1]=0;
		while(k){
			if(k&1)res=res*a;
			a=a*a;
			k>>=1;
		}
		return res;
	}
	void print(){
		for(rint i=0;i<2;i++,puts(""))
			for(rint j=0;j<2;j++)
				printf("%d ",x[i][j]);
	}
}f[N],g[N],I,m1,m2;
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx;
void Ins(rint a,rint b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
void dfs1(rint u,rint fa){
	f[u]=I;
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa)continue;
		dfs1(v,u);
		f[u]=f[u]+f[v]*m1;
	}
}
void dfs2(rint u,rint fa){
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa)continue;
		g[v]=(g[u]-f[v]*m1)*m1+f[v];
		dfs2(v,u);
	}
}
int main(){
	I.x[0][0]=I.x[1][1]=1;
	rint n=read();
	rll A,k;
	scanf("%lld%lld",&A,&k);k%=p;++A;
	for(rint i=2;i<=n;i++){
		rint x=read(),y=read();
		Ins(x,y);Ins(y,x);
	}
	rll fac=fpow(fpow(k-1,n),A);
	rll inv=fpow(fpow(k-1,p-2),A);
	m1.x[0][0]=Del(k,2)*fpow(k-1,p-2)%p;
	m1.x[0][1]=Del(k,1)*fpow(k-1,p-2)%p;
	m1.x[1][0]=fpow(k-1,p-2);
	m1.x[1][1]=0;
	m2=m1;
	for(rll t=A-1;t;t>>=1){
		if(t&1)m2=m2*m1;
		m1=m1*m1;
	}
	m1=m2;
	dfs1(1,0);
	g[1]=f[1];
	dfs2(1,0);
	Mat res;
	memset(res.x,0,sizeof(res.x));
	for(rint i=1;i<=n;i++)
		res=res+g[i];
	m1.x[0][0]=Del(k,2);
	m1.x[0][1]=Del(k,1);
	m1.x[1][0]=1;
	m1.x[1][1]=0;
	res=res*(m1^(A-1));
	printf("%lld\n",res.x[0][1]%p*inv%p*fac%p*k%p);
	return 0;
}

正方形

给定一张有障碍的网格图，给出一个初始的正方形，要求只上下左右平移并且不碰触障碍，询问能不能到达终点。

考虑左下角的路径，这个正方形可以通过某个点当且仅当以这个点为左下角的最大正方形的边长不小于给定正方形，所以考虑网格上两个点形成的边，一条边有贡献当且仅当两个格子都满足上述限制，所以直接离线然后排序即可，注意一个小细节，即对于每个点判断初始时会不会被挡住。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=1e3+10;
char s[N];
int f[N][N],fa[N*N],idx[N][N],cnt;
struct Node{
	int id,x,y,xx,yy,w;
	bool operator < (const Node&A)const{
		return w>A.w;
	}
}ask[N*N];
bool ans[N*N];
struct Edge{
	int fr,to;
};
vector<Edge> vec[N];
inline int find(rint x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
int main(){
	rint n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	for(rint i=1;i<=n;i++){
		scanf("%s",s+1);
		for(rint j=1;j<=m;j++){
			idx[i][j]=++cnt;fa[cnt]=cnt;
			if(s[j]=='1')f[i][j]=0;
			else f[i][j]=min(f[i-1][j],min(f[i-1][j-1],f[i][j-1]))+1;
			vec[min(f[i][j],f[i-1][j])].push_back((Edge){idx[i][j],idx[i-1][j]});
			vec[min(f[i][j],f[i][j-1])].push_back((Edge){idx[i][j],idx[i][j-1]});
		}
	}
	for(rint i=1;i<=q;i++)
		scanf("%d%d%d%d%d",&ask[i].x,&ask[i].y,&ask[i].xx,&ask[i].yy,&ask[i].w),ask[i].id=i;
	sort(ask+1,ask+q+1);
	for(rint i=1e3,j=1;i;i--){
		for(Edge v:vec[i])
			fa[find(v.fr)]=find(v.to);
		while(j<=q&&ask[j].w==i){
			if(ask[j].x==ask[j].xx&&ask[j].y==ask[j].yy)ans[ask[j].id]=f[ask[j].x][ask[j].y]>=ask[j].w;
			else ans[ask[j].id]=find(idx[ask[j].x][ask[j].y])==find(idx[ask[j].xx][ask[j].yy]);
			j++;
		}
	}
	for(rint i=1;i<=q;i++)
		puts(ans[i]?"Yes":"No");
	return 0;
}

计数

给定一个 $0/1$ 串，要求所有的子序列中满足中心对称的点对个数。

考虑直接推式子然后 $NTT$ 即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
#define ull unsigned long long
const int N=1<<18;
const int p=998244353;
inline int Add(rint x,rint y){x+=y;return x>=p?x-p:x;}
inline int Del(rint x,rint y){x-=y;return x>=0?x:x+p;}
inline ll Mul(rll x,rll y ){x*=y;return x>=p?x%p:x;}
ll fpow(rll a,rll b){
	rll res=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)res=res*a%p;
	return res;
}
char s[N];
int pw[N],fac[N],inv[N],w[N],r[N],f[N],g[N],cnt[N],pd,n,t;
ll res;
void ntt(rint n,rint *a,rint typ){
	if(pd!=n){
		for(rint i=0;i<n;i++)
			r[i]=(r[i>>1]>>1)|((i&1)?n>>1:0);
		pd=n;
	}
	for(rint i=0;i<n;i++)
		if(i<r[i])swap(a[i],a[r[i]]);
	for(rint mid=1;mid<n;mid<<=1)
	for(rint i=0;i<n;i+=mid<<1)
	for(rint j=0;j<mid;j++)
		t=Mul(w[mid+j],a[i+j+mid]),a[i+j+mid]=Del(a[i+j],t),a[i+j]=Add(a[i+j],t);
	if(~typ)return ;
	t=fpow(n,p-2);reverse(a+1,a+n);
	for(rint i=0;i<n;i++)
		a[i]=Mul(a[i],t);
}
void dfs(rint l,rint r){
	if(r-l<=180){
		for(rint i=l;i<=r;i++)
			for(rint j=i+1;j<=r;j++)
				if(s[i]==s[j])
					cnt[j-i]=Add(cnt[j-i],Mul(inv[i-1],inv[n-j]));
		return ;
	}
	rint mid=l+r>>1;
	dfs(l,mid);dfs(mid+1,r);
	rint Max=1,len=r-l+1;
	while(Max<len)Max<<=1;
	for(rint i=l;i<=mid;i++)
		g[i-l]=(s[i]=='0')?inv[i-1]:0;
	for(rint i=mid+1;i<=r;i++)
		f[i-l]=(s[i]=='0')?inv[n-i]:0;
	ntt(Max,f,-1);ntt(Max,g,1);
	for(rint i=0;i<Max;i++)
		f[i]=Mul(f[i],g[i]),g[i]=0;
	ntt(Max,f,1);
	for(rint i=1;i<len;i++)
		res+=Mul(Mul(f[i],pw[i-1]),fac[n-i-1]),f[i]=0;
	for(rint i=l;i<=mid;i++)
		g[i-l]=(s[i]=='1')?inv[i-1]:0;
	for(rint i=mid+1;i<=r;i++)
		f[i-l]=(s[i]=='1')?inv[n-i]:0;
	ntt(Max,f,-1);ntt(Max,g,1);
	for(rint i=0;i<Max;i++)
		f[i]=Mul(f[i],g[i]),g[i]=0;
	ntt(Max,f,1);
	for(rint i=1;i<len;i++)
		cnt[i]=Add(cnt[i],f[i]),f[i]=0;
}
int main(){
	w[N/2]=1;w[N/2+1]=t=fpow(3,(p-1)/N);
	for(rint i=N/2+2;i<N;i++)w[i]=Mul(w[i-1],t);
	for(rint i=N/2-1;i;i--)w[i]=w[i<<1];
	scanf("%s",s+1);n=strlen(s+1);
	fac[0]=fac[1]=inv[0]=inv[1]=pw[0]=1;pw[1]=2;
	for(rint i=2;i<=n;i++){
		fac[i]=Mul(fac[i-1],i);
		inv[i]=Del(0,Mul(p/i,inv[p%i]));
		pw[i]=(pw[i-1]<<1)%p;
	}
	for(rint i=2;i<=n;i++)
		inv[i]=Mul(inv[i-1],inv[i]);
	dfs(1,n);
	for(rint i=1;i<=n;i++)
		res+=Mul(Mul(cnt[i],pw[i-1]),fac[n-i-1]);
	printf("%lld\n",res%p);
	return 0;
}

硬币游戏

有 $n$ 堆硬币，每堆硬币的价值由上到下依次为 $a_i,b_i,a_i$ ，取一枚硬币必须取走它上边的所有硬币，对于体积为 $1-k$ 时分别求出答案。

考虑若 $a_i>b_i$ 那么在取走第一枚 $a_i$ 之后，剩下的两枚硬币一定是一起被取走的。

然后若 $a_i<b_i$ 那么前两枚硬币一定是一起取走的，于是可以得到一个结论，每堆硬币可以分为 $a_i+b_i$ 和 $a_i$ 两堆硬币，也就是说，现在相当于 $2n$ 个物品做 $0/1$ 背包，而不是做有依赖的背包了。

由于体积只有两个，所以可以对两种体积分别排序，然后考虑取哪一个体积的物品。

对于增加一个体积，只放一个体积的物品一定更优，对于两个体积的考虑回退一步即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=5e6+10;
int n,k,a[N],b[N];
int threshold=10000000;
unsigned long long k1,k2;
unsigned long long xorShift128Plus(){
	unsigned long long k3=k1,k4=k2;
	k1=k4;
	k3^=k3<<23;
	k2=k3^k4^(k3>>17)^(k4>>26);
	return k2+k4;
}
void gen(){
	scanf("%d%d%llu%llu",&n,&k,&k1,&k2);
	for(rint i=1;i<=n;i++){
		a[i]=xorShift128Plus()%threshold+1;
		b[i]=xorShift128Plus()%threshold+1;
	}
}
struct Node{
	int id,val;
	bool operator < (const Node&A)const{
		return val>A.val;
	}
}q1[N*3],q2[N*3];
int main(){
	gen();
	for(rint i=1;i<=n;i++){
		q1[i]=(Node){i,a[i]};
		q2[i]=(Node){i,a[i]+b[i]};
	}
	sort(q1+1,q1+n+1);
	sort(q2+1,q2+n+1);
	rint tp1=1,tp2=1;
	rll res=0,res2=0;
	for(rint i=1;i<=k;i++){
		if(tp1<=n&&tp2<=n){
			if(q1[tp1].val+q1[tp1+1].val<=q2[tp2].val){
				res2+=q1[tp1++].val;
				res^=res2;
				res2-=q1[--tp1].val;i++;
				if(i<=k){
					res2+=q2[tp2++].val;
					res^=res2;
				}
			}else {
				res2+=q1[tp1++].val;
				res^=res2;
			}
		}else if(tp1<=n){
			res2+=q1[tp1++].val;
			res^=res2;
		}else if(tp2<=n){
			res2+=b[q2[tp2].id];
			res^=res2;i++;
			if(i<=k){
				res2+=a[q2[tp2++].id];
				res^=res2;
			}
		}
	}
	printf("%lld\n",res);
	return 0;
}

序列计数

对一个字串，求某个区间中本质不同的非空子序列个数。

最大面积

给出若干个点，每次询问一个点与一个区间中所有点的叉积的和的最大值。

考虑直接推式子， $P\times A=P_xA_y-A_xP_y$ ，不妨设 $x$ 的前缀和为 $s_x$ ， $y$ 的前缀和为 $s_y$ ，那么要求的实际上是 $\max_{l,r}P_x(s_{yr}-s_{yl-1})-P_y(s_{xr}-s_{xl-1})$ ，可以直接 $n^2$ 求出所有可能的点对然后直接在凸包上进行二分即可，注意特判纵坐标为 $0$ 的情况。

上述问题的主要时间复杂度在于求出全局的凸包，求这个可以考虑进行分治，考虑区间 $[l,r]$ ，考虑跨过区间中点的点形成的凸包，任意一个点都能够写成一个左区间的后缀和加上右区间的前缀和，所以可以对于两侧分别求一个凸包然后用闵可夫斯基和合并，最后统一跑一个大凸包即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
inline int read(){
	rint x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0',ch=getchar();}
	return x*f;
}
const int N=1e5+10;
const int maxlg=20;
struct Node{
	int x,y;
}a[N];
struct Pt{
	ll x,y;
	Pt operator + (const Pt&A)const{return (Pt){x+A.x,y+A.y};}
	Pt operator - (const Pt&A)const{return (Pt){x-A.x,y-A.y};}
	ll operator * (const Pt&A)const{return x*A.y-y*A.x;}
	bool operator < (const Pt&A)const{return x==A.x?y<A.y:x<A.x;}
}b1[N*maxlg],b2[N*maxlg],up[N*maxlg],down[N*maxlg],t[N<<1];
vector<Pt> vec,vec1,vec2;
int n,m,stk[N*maxlg],tp,tot1,tot2;
ll sx[N],sy[N];
bool cmp1(Pt a,Pt b){return a*b>0;}
bool cmp2(Pt a,Pt b){return a*b<0;}
void dfs(rint l,rint r){
	if(l==r){
		b1[++tot1]=(Pt){(ll)a[l].y,(ll)a[l].x};
		b2[++tot2]=(Pt){(ll)a[l].y,(ll)a[l].x};
		return ;
	}
	rint mid=l+r>>1;
	dfs(l,mid);dfs(mid+1,r);
	rll sx=0,sy=0;vec.clear();
	for(rint i=mid+1;i<=r;i++){
		sx+=a[i].y,sy+=a[i].x;
		vec.push_back((Pt){sx,sy});
	}
	sort(vec.begin(),vec.end());tp=0;
	for(rint i=0;i<vec.size();i++){
		while(tp>1&&(vec[i]-vec[stk[tp-1]])*(vec[stk[tp]]-vec[stk[tp-1]])>=0)tp--;
		stk[++tp]=i;
	}
	vec1.clear();
	for(rint i=1;i<=tp;i++)
		vec1.push_back(vec[stk[i]]);
	sx=sy=0;vec.clear();tp=0;
	for(rint i=mid;i>=l;i--){
		sx+=a[i].y,sy+=a[i].x;
		vec.push_back((Pt){sx,sy});
	}
	sort(vec.begin(),vec.end());
	for(rint i=0;i<vec.size();i++){
		while(tp>1&&(vec[i]-vec[stk[tp-1]])*(vec[stk[tp]]-vec[stk[tp-1]])>=0)tp--;
		stk[++tp]=i;
	}
	vec2.clear();
	for(rint i=1;i<=tp;i++)
		vec2.push_back(vec[stk[i]]);
	rint tt=0;
	for(rint i=1;i<vec1.size();i++)
		t[++tt]=vec1[i]-vec1[i-1];
	for(rint i=1;i<vec2.size();i++)
		t[++tt]=vec2[i]-vec2[i-1];
	sort(t+1,t+tt+1,cmp1);
	Pt now=vec1[0]+vec2[0];
	b1[++tot1]=now;
	for(rint i=1;i<=tt;i++){
		now=now+t[i];
		b1[++tot1]=now;
	}
	sx=0,sy=0;vec.clear();
	for(rint i=mid+1;i<=r;i++){
		sx+=a[i].y,sy+=a[i].x;
		vec.push_back((Pt){sx,sy});
	}
	sort(vec.begin(),vec.end());tp=0;
	for(rint i=0;i<vec.size();i++){
		while(tp>1&&(vec[i]-vec[stk[tp-1]])*(vec[stk[tp]]-vec[stk[tp-1]])<=0)tp--;
		stk[++tp]=i;
	}
	vec1.clear();
	for(rint i=1;i<=tp;i++)
		vec1.push_back(vec[stk[i]]);
	sx=sy=0;vec.clear();tp=0;
	for(rint i=mid;i>=l;i--){
		sx+=a[i].y,sy+=a[i].x;
		vec.push_back((Pt){sx,sy});
	}
	sort(vec.begin(),vec.end());
	for(rint i=0;i<vec.size();i++){
		while(tp>1&&(vec[i]-vec[stk[tp-1]])*(vec[stk[tp]]-vec[stk[tp-1]])<=0)tp--;
		stk[++tp]=i;
	}
	vec2.clear();
	for(rint i=1;i<=tp;i++)
		vec2.push_back(vec[stk[i]]);
	tt=0;
	for(rint i=1;i<vec1.size();i++)
		t[++tt]=vec1[i]-vec1[i-1];
	for(rint i=1;i<vec2.size();i++)
		t[++tt]=vec2[i]-vec2[i-1];
	sort(t+1,t+tt+1,cmp2);
	now=vec1[0]+vec2[0];
	b2[++tot2]=now;
	for(rint i=1;i<=tt;i++){
		now=now+t[i];
		b2[++tot2]=now;
	}
}
int main(){
	n=read(),m=read();
	for(rint i=1;i<=n;i++){
		a[i].x=read(),a[i].y=read();
		sx[i]=sx[i-1]+a[i].x;
		sy[i]=sy[i-1]+a[i].y;
	}
	rll tmp1=0,tmp2=0,tmp3=0,tmp4=0;
	for(rint i=1;i<=n;i++){
		tmp1=max(tmp1,sy[i]+tmp3);
		tmp2=min(tmp2,sy[i]+tmp4);
		tmp3=max(tmp3,-sy[i]);
		tmp4=min(tmp4,-sy[i]);
	}
	dfs(1,n);
	sort(b1+1,b1+tot1+1);tp=0;
	for(rint i=1;i<=tot1;i++){
		while(tp>1&&(b1[i]-b1[stk[tp-1]])*(b1[stk[tp]]-b1[stk[tp-1]])>=0)tp--;
		stk[++tp]=i;
	}
	for(rint i=1;i<=tp;i++)
		down[i]=b1[stk[i]];
	rint lim1=tp;sort(b2+1,b2+tot2+1);tp=0;
	for(rint i=1;i<=tot2;i++){
		while(tp>1&&(b2[i]-b2[stk[tp-1]])*(b2[stk[tp]]-b2[stk[tp-1]])<=0)tp--;
		stk[++tp]=i;
	}
	for(rint i=1;i<=tp;i++)
		up[i]=b2[stk[i]];
	rint lim2=tp;
	while(m--){
		rint px=read(),py=read();
		rll res=0;
		if(!py)res=max(px*tmp1,px*tmp2);
		else if(py<0){
			rint l=2,r=lim2,pos=1;
			while(l<=r){
				rint mid=l+r>>1;
				if(1.0L*(up[mid].y-up[mid-1].y)/(up[mid].x-up[mid-1].x)>=1.0L*px/py)pos=mid,l=mid+1;
				else r=mid-1;
			}
			res=px*up[pos].x-py*up[pos].y;
		}else {
			rint l=2,r=lim1,pos=1;
			while(l<=r){
				rint mid=l+r>>1;
				if(1.0L*(down[mid].y-down[mid-1].y)/(down[mid].x-down[mid-1].x)<=1.0L*px/py)pos=mid,l=mid+1;
				else r=mid-1;
			}
			res=px*down[pos].x-py*down[pos].y;
		}
		printf("%lld\n",max(res,0ll));
	}
	return 0;
}

战神归来

$n$ 个人坐地铁，第 $i$ 个人要从 $S_i$ 到 $E_i$ ，从第 $i$ 站到第 $j$ 站花费的代价是 $|i-j|$ ，一个人只能沿着自己原本的路线走，但是可以在某站停下来和别人交换地铁卡，这样的话就能够将起点设置为对方的起点从而达到逃票的效果，问最少支付多少钱并且给出方案。

首先考虑最少支付多少钱，可以考虑每一条边的贡献，如果有两个人走相反的方向，那么让这两个人换一下卡一定不劣，所以对于 $S_i<E_i$ 的给这一段加一，否则减一，那么最终一条边的绝对值就是对答案的贡献。

考虑构造方案，不难发现只需要在能够换卡的时候随便换就行了，所以只需要维护这个东西，发现两种走法不是很好在一起考虑，因为走的方向是反的，于是将方向统一，即维护一条从左向右的扫描线，对于从左向右的点，在它的起点处加入这条线，对于从右向左的点，在它的终点处加入这条线，对于每一种线加入时考虑与它相对的那种线是否存在，如果存在就直接让两条线换卡，否则就加入队列，注意弹出不合法也就是右边的那个点没有跨过当前扫描线的情况，注意到一次换卡会在较短的那条线处结束，所以应该在结束的时候重新把较长的线加入，除非两条线一样长，考虑一次换卡操作最多只需要操作三次，最多换 $n$ 次卡，并且最后需要走到终点，于是操作次数是 $4n$ 级别的。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=4e5+10;
const int M=1e6+10;
int cnt[M],S[N],E[N],pre[N],nxt[N],rd[N],tot;
vector<int> vec1[M],vec2[M],vec;
unordered_map<int,int> vis[N];
struct Node{int typ,u,v,pos;}ans[N];
struct Edge{int to,nxt;}e[N<<2];
int h[N],idx;
inline void Ins(rint a,rint b){e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;}
inline void mov(rint x,rint y,rint z){if(vis[x].find(y)!=vis[x].end())return ;vis[x][y]=++tot;ans[tot]=(Node){0,x,y,z};}
inline void chg(rint x,rint y,rint z){ans[++tot]=(Node){1,x,y,z};}
struct Node2{
	int x,y;
	bool operator < (const Node2&A)const{
		return y<A.y;
	}
};
int match[N],q[N],arr[N],hh,tt;
struct Heap{
	Node2 val[N];
	int cnt;
	bool empty(){return cnt==0;}
	Node2 top(){return val[1];}
	void push(Node2 v){
		val[++cnt]=v;
		for(rint p1=cnt,p2=cnt>>1;p2;p1>>=1,p2>>=1){
			if(val[p1]<val[p2])
				swap(val[p1],val[p2]);
			else break;
		}
	}
	void pop(){
		swap(val[cnt],val[1]);cnt--;
		for(rint x=1;;){
			rint ls=x<<1,rs=x<<1|1;
			if(rs<=cnt&&val[rs]<val[ls]){
				if(val[rs]<val[x])swap(val[x],val[rs]);
				else break;
				x=rs;
			}else if(ls<=cnt){
				if(val[ls]<val[x])swap(val[x],val[ls]);
				else break;
				x=ls;
			}else break;
		}
	}
}q1,q2,q3;
void topsort(){
	hh=0;tt=-1;rint at=0;
	for(rint i=1;i<=tot;i++)
		(!rd[i])?q[++tt]=i:0;
	while(hh<=tt){
		rint u=q[hh++];
		arr[++at]=u;
		for(rint i=h[u];i;i=e[i].nxt){
			rint v=e[i].to;
			(!--rd[v])?q[++tt]=v:0;
		}
	}
}
inline int read(){
	rint x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
	return x;
}
char stk[20];
int tp;
inline void print(rint x){
	if(!x)putchar('0');
	else {
		tp=0;
		while(x)
			stk[++tp]=x%10+'0',x/=10;
		while(tp)
			putchar(stk[tp--]);
	}
}
int main(){
	rint T=read();
	while(T--){
		memset(nxt,0,sizeof(nxt));
		memset(rd,0,sizeof(rd));
		memset(h,0,sizeof(h));idx=0;
		memset(cnt,0,sizeof(cnt));tot=0;
		rint n=read(),m=read();
		for(rint i=1;i<=n;i++){
			S[i]=read();E[i]=read();
			cnt[S[i]]++,cnt[E[i]]--;
			if(S[i]<E[i])vec1[S[i]].push_back(i);
			else vec2[E[i]].push_back(i);
			vis[i].clear();
			vis[i][S[i]]=0;
		}
		rll res=0;
		for(rint i=1;i<=m;i++){
			cnt[i]+=cnt[i-1];
			res+=abs(cnt[i]);
			while(!q1.empty()&&q1.top().y==i)q1.pop();
			while(!q2.empty()&&q2.top().y==i)q2.pop();
			while(!q3.empty()&&q3.top().y==i){
				rint x=q3.top().x;q3.pop();
				match[match[x]]=0;
				if(S[match[x]]<E[match[x]]&&E[match[x]]!=i)q1.push((Node2){match[x],E[match[x]]});
				if(S[match[x]]>E[match[x]]&&S[match[x]]!=i)q2.push((Node2){match[x],S[match[x]]});
				match[x]=0;
			}
			while(!q1.empty()&&!q2.empty()){
				Node2 x=q1.top(),y=q2.top();
				q1.pop();q2.pop();
				match[x.x]=y.x;match[y.x]=x.x;
				mov(x.x,i,i);mov(y.x,i,i);chg(x.x,y.x,i);
				if(x.y<y.y)q3.push(x);
				else q3.push(y);
			}
			for(rint v:vec1[i]){
				if(!q2.empty()){
					Node2 u=q2.top();q2.pop();
					match[u.x]=v;match[v]=u.x;
					mov(u.x,i,i);mov(v,i,i);chg(u.x,v,i);
					if(u.y<E[v])q3.push((Node2){u.x,u.y});
					else q3.push((Node2){v,E[v]});
				}else q1.push((Node2){v,E[v]});
			}
			for(rint v:vec2[i]){
				if(!q1.empty()){
					Node2 u=q1.top();q1.pop();
					match[u.x]=v;match[v]=u.x;
					mov(u.x,i,i);mov(v,i,i);chg(u.x,v,i);
					if(u.y<S[v])q3.push((Node2){u.x,u.y});
					else q3.push((Node2){v,S[v]});
				}else q2.push((Node2){v,S[v]});
			}
			vec1[i].clear();
			vec2[i].clear();
		}
		for(rint i=1;i<=n;i++){
			mov(i,E[i],E[i]);
			vec.clear();
			for(auto v:vis[i])
				vec.push_back(v.first);
			if(S[i]<E[i])sort(vec.begin(),vec.end(),[](rint x,rint y){return x<y;});
			else sort(vec.begin(),vec.end(),[](rint x,rint y){return x>y;});
			rint lst=0;pre[i]=vis[i][vec[1]];
			for(rint j=1;j<vec.size();j++){
				rint x=vis[i][vec[j]];
				nxt[lst]=x;
				if(lst)Ins(lst,x),rd[x]++;
				lst=x;
			}
		}
		for(rint i=1;i<=tot;i++){
			if(ans[i].typ==1){
				rint x=vis[ans[i].u][ans[i].pos],y=vis[ans[i].v][ans[i].pos];
				if(x)Ins(x,i),rd[i]++;
				if(x&&nxt[x])Ins(i,nxt[x]),rd[nxt[x]]++;
				else if(ans[i].pos!=E[ans[i].u])Ins(i,pre[ans[i].u]),rd[pre[ans[i].u]]++;
				if(y)Ins(y,i),rd[i]++;
				if(y&&nxt[y])Ins(i,nxt[y]),rd[nxt[y]]++;
				else if(ans[i].pos!=E[ans[i].v])Ins(i,pre[ans[i].v]),rd[pre[ans[i].v]]++;
			}
		}
		topsort();
		printf("%lld %d\n",res,tot);
		for(rint i=1;i<=tot;i++)
			print(ans[arr[i]].typ),putchar(' '),print(ans[arr[i]].u),putchar(' '),print(ans[arr[i]].v),putchar('\n');
	}
	return 0;
}

组合数问题

给定 $n,m$ ，求 $\sum_{i=0}^n(-1)^i\sum_{j=0}^nj^m\binom{j}{i}(m+i)^j$ 。

首先发现这个 $i$ 在最外边但是只有一个 $-1$ 比较浪费，所以考虑把 $j$ 换出来，然后大力推式子。

\begin{aligned} \sum_{i=0}^n(-1)^i\sum_{j=0}^nj^m\binom{j}{i}(m+i)^j&=\sum_{j=0}^nj^m\sum_{i=0}^n(-1)^i\binom{j}{i}\sum_{k=0}^j\binom{j}{k}m^{j-k}i^k\\ &=\sum_{j=0}^nj^m\sum_{k=0}^j\binom{j}{k}m^{j-k}\sum_{i=0}^n(-1)^i\binom{j}{i}\sum_{x=0}^i\binom{i}{x}{k \brace x}x!\\ &=\sum_{j=0}^nj^m\sum_{k=0}^j\binom{j}{k}m^{j-k}\sum_{x=0}^n{k \brace x}x!\sum_{i=0}^n(-1)^i\binom{j}{i}\binom{i}{x}\\ &=\sum_{j=0}^nj^m\sum_{k=0}^j\binom{j}{k}m^{j-k}\sum_{x=0}^n{k \brace x}x!\sum_{i=0}^n(-1)^i\binom{j}{x}\binom{j-x}{i-x}\\ &=\sum_{j=0}^nj^m\sum_{k=0}^j\binom{j}{k}m^{j-k}\sum_{x=0}^n\binom{j}{x}{k \brace x}x!\sum_{i=0}^n(-1)^i\binom{j-x}{i-x}\\ &=\sum_{j=0}^nj^m\sum_{k=0}^j\binom{j}{k}m^{j-k}\sum_{x=0}^n\binom{j}{x}{k \brace x}x!(-1)^x\sum_{i=0}^n(-1)^{i-x}\binom{j-x}{i-x}\\ &=\sum_{j=0}^nj^m\sum_{k=0}^j\binom{j}{k}m^{j-k}\sum_{x=0}^n\binom{j}{x}{k \brace x}x!(-1)^x\sum_{i=0}^n(-1)^{i}\binom{j-x}{i}\\ &=\sum_{j=0}^nj^m\sum_{k=0}^j\binom{j}{k}m^{j-k}\sum_{x=0}^n\binom{j}{x}{k \brace x}x!(-1)^x[j==x]\\ &=\sum_{j=0}^nj^m\sum_{k=0}^j\binom{j}{k}m^{j-k}{k \brace j}j!(-1)^j\\ &=\sum_{j=0}^nj^mj!(-1)^j\\ \end{aligned}

然后就是一个十分好算的式子，直接算就行了，注意以后推式子的时候一直往下推，推到不能推再回溯。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=1e5+10;
const int p=998244353;
ll fac[N],inv[N];
ll fpow(rll a,rll b){
	rll res=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)res=res*a%p;
	return res;
}
int main(){
	rint n,m;
	scanf("%d%d",&n,&m);
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(rint i=2;i<=n;i++){
		fac[i]=fac[i-1]*i%p;
		inv[i]=p-p/i*inv[p%i]%p;
	}
	for(rint i=2;i<=n;i++)
		inv[i]=inv[i]*inv[i-1]%p;
	rll res=0;
	for(rint i=0;i<=n;i++)
		res+=(i&1?-1:1)*fpow(i,m)*fac[i]%p;
	res=(res%p+p)%p;
	printf("%lld\n",res);
	return 0;
}

三角形

定义一个点是好点当且仅当这个点的坐标 $1\leq x \leq n$ ， $1\leq y \leq m$ ，并且这个点的坐标都是整数。

求有多少个三角形的三个顶点都是好点并且三角形内不包含其它好点。

于是发现对于所有的三角形，其最长边一定在一个矩形的对角线上，所以只需要枚举一条对角线算贡献即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=2e7+10;
const int p=1e9+7;
inline int Add(rint x,rint y){x+=y;return x>=p?x-p:x;}
int pri[N],s[N];
bool npri[N];
unordered_map<ll,ll> dp1,dp2,dp3,dp4;
ll S1(rll n){
	if(n<=2e7)return s[n];
	if(dp1.find(n)!=dp1.end())return dp1[n];
	rll res=1;
	for(rll l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		res-=(r-l+1)%p*S1(n/l)%p;
	}
	return dp1[n]=(res%p+p)%p;
}
ll solve1(rll n,rll m){
	pri[0]=0;s[1]=1;
	memset(npri,0,sizeof(npri));
	for(rint i=2;i<=2e7;i++){
		if(!npri[i]){
			pri[++pri[0]]=i;
			s[i]=p-1;
		}
		for(rint j=1;j<=pri[0]&&i*pri[j]<=2e7;j++){
			npri[i*pri[j]]=1;
			if(i%pri[j]==0){
				s[i*pri[j]]=0;
				break;
			}
			s[i*pri[j]]=p-s[i];
		}
	}
	for(rint i=1;i<=2e7;i++)
		s[i]=Add(s[i-1],s[i]);
	rll res=0;
	for(rll l=1,r;l<=n&&l<=m;l=r+1){
		r=min(n/(n/l),m/(m/l));
		res+=(n/l%p)*(m/l%p)%p*(S1(r)-S1(l-1))%p;
	}
	res=(res%p+p)%p*n%p*m%p;
	return res;
}
inline ll sum1(rll n){
	n%=p;return n*(n+1)%p*(p+1>>1)%p;
}
inline ll sum2(rll n){
	n%=p;return (2*n+1)*n%p*(n+1)%p*166666668%p;
}
ll S2(rll n){
	if(n<=2e7)return s[n];
	if(dp2.find(n)!=dp2.end())return dp2[n];
	rll res=1;
	for(rll l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		res-=(sum1(r)-sum1(l-1))*S2(n/l)%p;
	}
	return dp2[n]=(res%p+p)%p;
}
ll solve2(rll n,rll m){
	pri[0]=0;s[1]=1;
	memset(npri,0,sizeof(npri));
	for(rint i=2;i<=2e7;i++){
		if(!npri[i]){
			pri[++pri[0]]=i;
			s[i]=1ll*(p-1)*i%p;
		}
		for(rint j=1;j<=pri[0]&&i*pri[j]<=2e7;j++){
			npri[i*pri[j]]=1;
			if(i%pri[j]==0){
				s[i*pri[j]]=0;
				break;
			}
			s[i*pri[j]]=1ll*(p-s[i])*pri[j]%p;
		}
	}
	for(rint i=1;i<=2e7;i++)
		s[i]=Add(s[i-1],s[i]);
	rll res=0;
	for(rll l=1,r;l<=n&&l<=m;l=r+1){
		r=min(n/(n/l),m/(m/l));
		res+=(S2(r)-S2(l-1))*((n/l)*sum1(m/l)%p*n%p+(m/l)*sum1(n/l)%p*m%p)%p;
	}
	return (res%p+p)%p;
}
ll S4(rll n){
	if(n<=2e7)return s[n];
	if(dp4.find(n)!=dp4.end())return dp4[n];
	rll res=1;
	for(rll l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		res-=(sum2(r)-sum2(l-1))%p*S4(n/l)%p;
	}
	return dp4[n]=(res%p+p)%p;
}
ll solve4(rll n,rll m){
	pri[0]=0;s[1]=1;
	memset(npri,0,sizeof(npri));
	for(rint i=2;i<=2e7;i++){
		if(!npri[i]){
			pri[++pri[0]]=i;
			s[i]=1ll*(p-1)*i%p*i%p;
		}
		for(rint j=1;j<=pri[0]&&i*pri[j]<=2e7;j++){
			npri[i*pri[j]]=1;
			if(i%pri[j]==0){
				s[i*pri[j]]=0;
				break;
			}
			s[i*pri[j]]=1ll*(p-s[i])*pri[j]%p*pri[j]%p;
		}
	}
	for(rint i=1;i<=2e7;i++)
		s[i]=Add(s[i-1],s[i]);
	rll res=0;
	for(rll l=1,r;l<=n&&l<=m;l=r+1){
		r=min(n/(n/l),m/(m/l));
		res+=(S4(r)-S4(l-1))*sum1(n/l)%p*sum1(m/l)%p;
	}
	return (res%p+p)%p;
}
int main(){
	rll n,m;
	scanf("%lld%lld",&n,&m);
	rll res=solve1(n,m)-solve2(n,m)+solve4(n,m);
	res=(res%p+p)*4%p;
	printf("%lld\n",res%p);
	return 0;
}

树

读题题。

考虑给出的函数 $f_u$ ，是从上向下考虑的，这样做并不是很好考虑，因为一个点可能有很多子树，可以将它反过来，枚举终点，那么跳到它的可能性是 $2^d$ ，所以只需要维护 $\sum 2^d$ 即可，考虑最终每个点的贡献，是类似 $k\times 2^d+b$ 的形式，所以只需要用树状数组维护 $k$ 即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=5e5+10;
const int p=998244353;
ll fpow(rll a,rll b){
	rll res=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)res=res*a%p;
	return res;
}
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx;
void Ins(rint a,rint b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
int pt[N];
ll sum[N];
void dfs(rint u,rint pw){
	sum[pt[u]]+=pw;
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		dfs(v,(pw<<1)%p);
	}
}
int siz[N],dfn[N],rk[N],Time;
ll tr[N],val[N],s[N];
void update(rint x,rll v){
	for(;x<=Time;x+=x&-x)
		tr[x]+=v;
}
ll query(rint x){
	rll res=0;
	for(;x;x&=x-1)
		res+=tr[x];
	return res%p;
}
void dfs(rint u){
	siz[u]=1;dfn[u]=++Time;rk[Time]=u;
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		val[v]=(val[u]<<1)%p;
		dfs(v);
		siz[u]+=siz[v];
	}
}
int main(){
	rint n;
	scanf("%d",&n);
	for(rint i=2;i<=n;i++){
		rint x;
		scanf("%d",&x);
		Ins(x,i);
	}
	for(rint i=1;i<=n;i++)
		scanf("%d",&pt[i]);
	dfs(1,1);
	memset(h,0,sizeof(h));idx=0;
	scanf("%d",&n);sum[1]%=p;
	for(rint i=2;i<=n;i++){
		rint x;
		scanf("%d",&x);
		Ins(x,i);
		sum[i]%=p;
	}
	val[1]=1;
	dfs(1);
	rll res=0;
	for(rint i=1;i<=n;i++){
		res+=sum[i];
		s[i]=(s[i-1]+val[rk[i]])%p;
	}
	printf("%lld\n",res%p);
	rint q;
	scanf("%d",&q);
	while(q--){
		rint x,y;
		scanf("%d%d",&x,&y);
		rll now=(query(dfn[x])*val[x]+sum[x])%p*fpow(val[y],p-2)*2%p;
		update(dfn[y],now);
		update(dfn[y]+siz[y],p-now);
		res+=now*(s[dfn[y]+siz[y]-1]-s[dfn[y]-1])%p;
		res=(res%p+p)%p;
		printf("%lld\n",res%p);
	}
	return 0;
}

网格

给出一张网格图，有一些格子不能走，只能向下或者向右走，每次询问从一个点能不能走到另一个点。

有一个显然的 $\frac{n^4}{32}$ 的做法，不过貌似过不去，考虑进行常数优化，首先可以手写 $bitset$ 做到除数是 $64$ ，然后可以在里边拆出来一位表示行，这样可以再除以 $2$ ，最后是 $\frac{n^4}{128}$ ，应该可以过。

考虑另一个比较靠谱的做法，对整张图进行分治，每次考虑跨过分治中心的询问，并把不跨过的向两侧递归，最后的时间复杂度是 $\frac{nm^2logn}{32}$ 。

其实已经想到了可以找几个特殊点，但是一直不知道找什么特殊点比较好，并且发现特殊点的做法是错的，没有扩展到找一条线就是对的，扩展了可能也不会做，因为没怎么用过分治，对于这种找点的问题可以进行分治，每次找中心然后分开递归。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=510;
char s[N][N];
bitset<N> f[N][N],g[N][N];
int n,m,q;
bool ans[600010];
struct Node{
	int id,x,y,xx,yy;
};
void dfs(rint l,rint r,vector<Node> vec){
	if(vec.empty())return ;
	rint mid=l+r>>1;
	for(rint i=1;i<=m;i++){
		g[mid][i].reset();
		if(s[mid][i]=='.')
			g[mid][i]=g[mid][i-1],g[mid][i].set(i);
	}
	for(rint i=m;i;i--){
		f[mid][i].reset();
		if(s[mid][i]=='.')
			f[mid][i]=f[mid][i+1],f[mid][i].set(i);
	}
	for(rint i=mid-1;i>=l;i--)
		for(rint j=m;j;j--){
			if(s[i][j]=='.')f[i][j]=f[i+1][j]|f[i][j+1];
			else f[i][j].reset();
		}
	for(rint i=mid+1;i<=r;i++)
		for(rint j=1;j<=m;j++){
			if(s[i][j]=='.')g[i][j]=g[i-1][j]|g[i][j-1];
			else g[i][j].reset();
		}
	vector<Node> vl,vr;
	for(Node v:vec){
		if(v.x>mid)vr.push_back(v);
		else if(v.xx<mid)vl.push_back(v);
		else ans[v.id]=(f[v.x][v.y]&g[v.xx][v.yy]).any();
	}
	dfs(l,mid-1,vl);
	dfs(mid+1,r,vr);
}
int main(){
	scanf("%d%d",&n,&m);
	for(rint i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	scanf("%d",&q);
	vector<Node> vec;
	for(rint i=1;i<=q;i++){
		rint x,y,xx,yy;
		scanf("%d%d%d%d",&x,&y,&xx,&yy);
		vec.push_back((Node){i,x,y,xx,yy});
	}
	dfs(1,n,vec);
	for(rint i=1;i<=q;i++)
		puts(ans[i]?"Yes":"No");
	return 0;
}

点分治

对一棵基环树进行点分治，求最后时间复杂度的期望值。

可以考虑任意两个点之间的贡献，一个点对另一个点有贡献，当且仅当存在一条路径使得在这条路径上，这个点是第一个被删除的，如果两个点间只有一条路径，那么最后的答案是显然的，如果有多条路径，还需要容斥一下。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=3e3+10;
const int p=1e9+7;
ll fpow(rll a,rll b){
	rll res=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)res=res*a%p;
	return res;
}
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx=1;
void Ins(rint a,rint b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
bool incir[N],vis[N];
vector<int> vec;
int inv[N],stk[N],tp;
void getcir(rint u,rint fa){
	stk[++tp]=u;
	vis[u]=1;
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(i==fa)continue;
		if(vis[v]){
			if(vec.empty()){
				for(rint j=tp;j;j--){
					rint x=stk[j];
					incir[x]=1;
					vec.push_back(x);
					if(x==v)break;
				}
			}
		}else getcir(v,i^1);
	}
	tp--;
}
int col[N],dis[N],dis2[N],fp[N][22];
void dfs(rint u,rint rt){
	col[u]=rt;dis[u]=dis[fp[u][0]]+1;
	for(rint i=0;fp[u][i];i++)
		fp[u][i+1]=fp[fp[u][i]][i];
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(incir[v]||v==fp[u][0])continue;
		fp[v][0]=u;
		dfs(v,rt);
	}
}
int lca(rint x,rint y){
	if(dis[x]<dis[y])swap(x,y);
	for(rint dt=dis[x]-dis[y],i=0;dt;i++,dt>>=1)
		if(dt&1)x=fp[x][i];
	if(x==y)return x;
	for(rint i=15;~i;i--)
		if(fp[x][i]!=fp[y][i])
			x=fp[x][i],y=fp[y][i];
	return fp[x][0];
}
int main(){
	rint n;
	scanf("%d",&n);
	for(rint i=1;i<=n;i++){
		rint x,y;
		scanf("%d%d",&x,&y);
		Ins(x,y);Ins(y,x);
	}
	inv[0]=inv[1]=1;
	for(rint i=2;i<=n;i++)
		inv[i]=p-1ll*p/i*inv[p%i]%p;
	getcir(1,0);
	rint r=0;
	for(rint x:vec){
		dis2[x]=++r;
		dfs(x,x);
	}
	rll res=0;
	for(rint x=1;x<=n;x++){
		for(rint y=1;y<=n;y++){
			if(col[x]==col[y])
				res+=inv[dis[x]+dis[y]-2*dis[lca(x,y)]+1];
			else {
				rint dt=abs(dis2[col[x]]-dis2[col[y]]);
				res+=inv[dis[x]+dis[y]+dt-1];
				res+=inv[dis[x]+dis[y]+r-dt-1];
				res-=inv[dis[x]+dis[y]+r-2];
			}
		}
	}
	res=(res%p+p)%p;
	printf("%lld\n",res);
	return 0;
}

染色

给定一个长度为 $n$ 的棋盘，要求对其染色，初始均为白色，要将某些格子染成黑色，有 $q$ 次询问，每次询问形如第 $x$ 个格子必须是白色，任意两个黑色格子之间的距离不小于 $k$ ，回答方案数对 $998244353$ 取模的结果。

首先不难想到一个 $dp$ 的写法，定义 $dp_i$ 表示最后一个黑色格子在 $i$ 的方案数，转移是一个类似前缀和的东西，不过要特殊考虑第 $x$ 个点，这个看上去就不是很方便，把它单步容斥掉，用总的减去它是黑色的方案，不妨设 $solve(n,k)$ 表示 $n$ 个格子，任意两个黑色格子的距离不小于 $k$
的方案数，那么答案显然是

solve(n,k)-solve(x-k-1,k)\times solve(n-x-k,k)

由于单次是 $O(n)$ 的并不能通过，所以考虑换一种做法，大概想到用组合数说不定可以推式子，那么考虑组合含义，可以钦定每个黑色格子之前必须放 $k-1$ 个白色格子，这样枚举黑色格子的个数，提前拿走若干白色格子，设有 $i$ 个黑色格子，不难得到答案是 $\binom{n-(i-1)(k-1)}{i}$ ，仔细思考一波后发现这个式子也不太好优化，考虑到它是 $O(n/k)$ 的，那么 $k$ 比较大的时候可以直接做，而对于 $k$ 比较小的情况可以分别跑一个 $dp$ 来预处理，所以最后时间复杂度是 $O(n\sqrt n)$ 。

想到的暴力不要轻易否定，说不定可以用来分治。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=2e5+10;
const int S=220;
const int p=998244353;
int ans[225][N],fac[N],inv[N],dp[N],s[N];
inline int Add(rint x,rint y){x+=y;return x>=p?x-p:x;}
ll C(rint n,rint m){
	if(n<m)return 0;
	return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;
}
ll solve(rint n,rint k){
	if(n<=0)return 1;
	if(k<=S)return ans[k][n];
	rll res=1;
	for(rint i=1;i<=n-i*k+k;i++)
		res+=C(n-i*k+k,i);
	return res%p;
}
int main(){
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(rint i=2;i<N;i++){
		fac[i]=1ll*fac[i-1]*i%p;
		inv[i]=p-1ll*p/i*inv[p%i]%p;
	}
	for(rint i=2;i<N;i++)
		inv[i]=1ll*inv[i-1]*inv[i]%p;
	rint n,m;
	scanf("%d%d",&n,&m);
	for(rint i=0;i<=S;i++){
		ans[i][0]=1;
		for(rint j=1;j<=n;j++){
			if(i+1<j)dp[j]=Add(s[j-i-1],1);
			else dp[j]=1;
			ans[i][j]=Add(s[j-1],1);
			ans[i][j]=Add(ans[i][j],dp[j]);
			s[j]=Add(s[j-1],dp[j]);
		}
	}
	while(m--){
		rint x,k;
		scanf("%d%d",&x,&k);--k;
		rll res=solve(n,k)-solve(x-k-1,k)*solve(n-x-k,k);
		res=(res%p+p)%p;
		printf("%lld\n",res);
	}
	return 0;
}

林克卡特树

给定一棵 $n$ 个点的有根树，每个点有点权，每次随机选择一个点权不为 $0$ 的点，进行 $Access$ 操作，并将这个点的点权减一，直到所有点的点权为 $0$ ，求最后所有实链的长度的 $k$ 次方的期望，需要对于每次修改维护答案，一次修改是将某一个点权沿一条边移动，操作时并不真正去减点权。

首先考虑 $k=1$ 的做法，由于期望的线性，可以考虑每条边的贡献，定义 $a_u$ 表示 $u$ 点权， $c_u$ 表示以 $u$ 为根的子树中 $a$ 的和，考虑每个点的父亲边的贡献，设其父亲是 $fa$ ，如果这条边有贡献那么 $fa$ 的子树内最后一次 $Access$ 的操作是在 $u$ 的子树中，这个概率是 $\frac{c_u}{c_{fa}}$ ，考虑最后一个位置的取值有 $c_{fa}$ 种，合法的有 $c_u$ 种。

有这个概率后一些问题就比较清晰明了了，可以考虑做一个 $dp[u][j]$ ，表示以 $u$ 为根的实链的 $j$ 次方的期望值，那么每次转移的时候用二项式定理展开即可，显然可以套一个动态 $dp$ 去维护，也显然很恶心，并且显然过不去，对于使用二项式定理的 $dp$ 优化几乎没有，所以考虑换一个做法。

不过貌似没有什么做法了，尝试一下直接枚举每条链的贡献，是

(1-\frac{c_u}{c_{fa}})\frac{c_v}{c_u}(d_v-d_u)^k

主要解释一下概率为什么是 $(1-\frac{c_u}{c_{fa}})\frac{a_v}{c_u}$ ，这两个看上去并不独立。

事实上可以先考虑大的子树，要求最后一个点不能是 $u$ 的子树内的，再考虑小子树，最后一个点必须在 $v$ 上边，注意到这样考虑是满足上述式子的，而如果先考虑小子树就不满足这个了，注意是看上去不满足，实际是满足的，原因是小子树要考虑的东西比较多，因为如果先确定小子树，那么大子树的排列方案并不能直接算，而是一个类似可重集的排列的东西，所以其实也满足。

这样的话拆一下式子，是

\sum_{i=0}^k\binom{k}{i}(-1)^i(\frac{1}{c_u}-\frac{1}{c_{fa}})\frac{1}{c_u}d_u^id_v^{k-i}a_v

可以对于含有 $u$ 的项和含有 $v$ 的项分别处理，注意对于 $fa$ 的单独维护。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=1e5+10;
const int p=998244353;
ll fpow(rll a,rll b){
	rll res=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)res=res*a%p;
	return res;
}
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx;
void Ins(rint a,rint b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
int a[N],siz[N],siz2[N],d[N],fa[N],dfn[N],Time;
void dfs1(rint u){
	siz[u]=a[u];dfn[u]=++Time;siz2[u]=1;
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa[u])continue;
		fa[v]=u;
		d[v]=d[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		siz2[u]+=siz2[v];
	}
}
int n,m,k;
ll res,C[20][20];
inline int Add(rint x,rint y){x+=y;return x>=p?x-p:x;}
inline int Del(rint x,rint y){x-=y;return x>=0?x:x+p;}
struct Node{
	int val[11];
	Node(){memset(val,0,sizeof(val));}
	void operator += (const Node&A){
		for(rint i=0;i<=k;i++)
			val[i]=Add(val[i],A.val[i]);
	}
	Node operator + (const Node&A)const{
		Node res=*this;res+=A;
		return res;
	}
	friend Node operator ~ (const Node&A){
		Node res;
		for(rint i=0;i<=k;i++)
			res.val[i]=Del(0,A.val[i]);
		return res;
	}
}f1[N],f2[N],g[N],tr1[N],tr2[N];
void update1(rint x,Node v){
	for(;x<=n;x+=x&-x)
		tr1[x]+=v;
}
Node query1(rint x){
	Node res;
	for(;x;x&=x-1)
		res+=tr1[x];
	return res;
}
void update2(rint x,Node v){
	for(;x<=n;x+=x&-x)
		tr2[x]+=v;
}
Node query2(rint x){
	Node res;
	for(;x;x&=x-1)
		res+=tr2[x];
	return res;
}
int inv[N],pw[N][11];
void dfs2(rint u){
	inv[u]=fpow(siz[u],p-2);
	for(rint i=0;i<=k;i++){
		f1[u].val[i]=1ll*pw[d[u]][i]*inv[u]%p;
		f2[u].val[i]=1ll*pw[d[u]+1][i]*(p-inv[u])%p;
		g[u].val[i]=1ll*pw[d[u]][i]*a[u]%p;
	}
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa[u])continue;
		dfs2(v);
	}
}
int main(){
	for(rint i=0;i<=10;i++){
		C[i][0]=1;
		for(rint j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	scanf("%d%d%d",&n,&m,&k);
	for(rint i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(rint i=0;i<=n+1;i++){
		pw[i][0]=1;
		for(rint j=1;j<=k;j++)
			pw[i][j]=1ll*pw[i][j-1]*i%p;
	}
	for(rint i=2;i<=n;i++){
		rint x,y;
		scanf("%d%d",&x,&y);
		Ins(x,y);Ins(y,x);
	}
	dfs1(1);
	dfs2(1);
	for(rint u=1;u<=n;u++){
		update1(dfn[u],f1[u]);
		update1(dfn[u]+siz2[u],~f1[u]);
		update1(dfn[u]+1,f2[u]);
		update1(dfn[u]+siz2[u],~f2[u]);
		update2(dfn[u],g[u]);
	}
	for(rint i=1;i<=n;i++){
		Node now=query1(dfn[i]);
		for(rint j=0,pw=1;j<=k;j++,pw=-pw)
			res+=C[k][j]*now.val[j]%p*g[i].val[k-j]%p*pw;
	}
	res=(res%p+p)%p;
	printf("%lld\n",res);
	while(m--){
		rint x,y;
		scanf("%d%d",&x,&y);
		Node now=query1(dfn[x]);
		for(rint j=0,pw=1;j<=k;j++,pw=-pw)
			res-=C[k][j]*now.val[j]%p*g[x].val[k-j]%p*pw;
		now=query1(dfn[y]);
		for(rint j=0,pw=1;j<=k;j++,pw=-pw)
			res-=C[k][j]*now.val[j]%p*g[y].val[k-j]%p*pw;
		if(fa[x]==y){
			now=query2(dfn[x]+siz2[x]-1)+(~query2(dfn[x]-1));
			for(rint j=0,pw=1;j<=k;j++,pw=-pw)
				res-=C[k][j]*f1[x].val[j]%p*now.val[k-j]%p*pw;
			now=query2(dfn[x]+siz2[x]-1)+(~query2(dfn[x]));
			for(rint j=0,pw=1;j<=k;j++,pw=-pw)
				res-=C[k][j]*f2[x].val[j]%p*now.val[k-j]%p*pw;
			siz[x]--;a[x]--;a[y]++;
			inv[x]=fpow(siz[x],p-2);
			update1(dfn[x],~f1[x]);
			update1(dfn[x]+siz2[x],f1[x]);
			update1(dfn[x]+1,~f2[x]);
			update1(dfn[x]+siz2[x],f2[x]);
			update2(dfn[x],~g[x]);
			update2(dfn[y],~g[y]);
			for(rint i=0;i<=k;i++){
				f1[x].val[i]=1ll*pw[d[x]][i]*inv[x]%p;
				f2[x].val[i]=1ll*pw[d[x]+1][i]*(p-inv[x])%p;
				g[x].val[i]=1ll*pw[d[x]][i]*a[x]%p;
				g[y].val[i]=1ll*pw[d[y]][i]*a[y]%p;
			}
			update1(dfn[x],f1[x]);
			update1(dfn[x]+siz2[x],~f1[x]);
			update1(dfn[x]+1,f2[x]);
			update1(dfn[x]+siz2[x],~f2[x]);
			update2(dfn[x],g[x]);
			update2(dfn[y],g[y]);
			now=query2(dfn[x]+siz2[x]-1)+(~query2(dfn[x]-1));
			for(rint j=0,pw=1;j<=k;j++,pw=-pw)
				res+=C[k][j]*f1[x].val[j]%p*now.val[k-j]%p*pw;
			now=query2(dfn[x]+siz2[x]-1)+(~query2(dfn[x]));
			for(rint j=0,pw=1;j<=k;j++,pw=-pw)
				res+=C[k][j]*f2[x].val[j]%p*now.val[k-j]%p*pw;
		}else {
			now=query2(dfn[y]+siz2[y]-1)+(~query2(dfn[y]-1));
			for(rint j=0,pw=1;j<=k;j++,pw=-pw)
				res-=C[k][j]*f1[y].val[j]%p*now.val[k-j]%p*pw;
			now=query2(dfn[y]+siz2[y]-1)+(~query2(dfn[y]));
			for(rint j=0,pw=1;j<=k;j++,pw=-pw)
				res-=C[k][j]*f2[y].val[j]%p*now.val[k-j]%p*pw;
			siz[y]++;a[x]--;a[y]++;
			inv[y]=fpow(siz[y],p-2);
			update1(dfn[y],~f1[y]);
			update1(dfn[y]+siz2[y],f1[y]);
			update1(dfn[y]+1,~f2[y]);
			update1(dfn[y]+siz2[y],f2[y]);
			update2(dfn[x],~g[x]);
			update2(dfn[y],~g[y]);
			for(rint i=0;i<=k;i++){
				f1[y].val[i]=1ll*pw[d[y]][i]*inv[y]%p;
				f2[y].val[i]=1ll*pw[d[y]+1][i]*(p-inv[y])%p;
				g[x].val[i]=1ll*pw[d[x]][i]*a[x]%p;
				g[y].val[i]=1ll*pw[d[y]][i]*a[y]%p;
			}
			update1(dfn[y],f1[y]);
			update1(dfn[y]+siz2[y],~f1[y]);
			update1(dfn[y]+1,f2[y]);
			update1(dfn[y]+siz2[y],~f2[y]);
			update2(dfn[x],g[x]);
			update2(dfn[y],g[y]);
			now=query2(dfn[y]+siz2[y]-1)+(~query2(dfn[y]-1));
			for(rint j=0,pw=1;j<=k;j++,pw=-pw)
				res+=C[k][j]*f1[y].val[j]%p*now.val[k-j]%p*pw;
			now=query2(dfn[y]+siz2[y]-1)+(~query2(dfn[y]));
			for(rint j=0,pw=1;j<=k;j++,pw=-pw)
				res+=C[k][j]*f2[y].val[j]%p*now.val[k-j]%p*pw;
		}
		now=query1(dfn[x]);
		for(rint j=0,pw=1;j<=k;j++,pw=-pw)
			res+=C[k][j]*now.val[j]%p*g[x].val[k-j]%p*pw;
		now=query1(dfn[y]);
		for(rint j=0,pw=1;j<=k;j++,pw=-pw)
			res+=C[k][j]*now.val[j]%p*g[y].val[k-j]%p*pw;
		res=(res%p+p)%p;
		printf("%lld\n",res);
	}
	return 0;
}

异或粽子

每个点有一个取值区间 $[0,a_i]$ ，支持两种操作，第一种是令 $a_x=y$ ，第二种是询问区间 $[l,r]$ 的点的所有取值方案中，有多少的异或和在 $[L,R]$ 中。

考虑一个暴力的做法，对于每次转移相当于做一个异或卷积，所以在值域比较小的时候可以直接维护 $FWT$ 数组的区间积。

但是值域如果比较大就不太行了，考虑如何不把值域加到 $dp$ 的状态里边，注意到一直没有用到前缀和的性质，不过也确实不知道前缀和的性质，题解给出了一个十分强大的性质，不过貌似也比较显然，对于一个值域区间 $[c2^k,(c+1)2^k-1]$ ，一个数异或上这个区间得到的还是一个长度相同的值域区间，并且区间的左右端点只有高于第 $k$ 位的位置会改变，考虑为什么，原因是对于前 $k$ 位，区间中包含了前 $k$ 位的所有取值，在这种情况下异或是封闭的，所以只有高于第 $k$ 位会改变。

根据上边的性质，两个区间异或起来得到的还是一个区间，并且长度是原来较长的那个，所以我们实际上只需要把每个 $a_i$ 划分成若干个区间，然后每次在一个位置选择一个区间进行异或，这样的话只需要知道异或的区间的最大值，就能够知道最后值域区间的最大值，所以可以直接枚举这个最大值，考虑怎么得到值域范围的其它值，首先找一个划分区间的办法，可以将 $a_i$ 加上一，然后二进制分解，注意分的区间要从大到小，因为要保证它始终是 $[c2^k,(c+1)2^k-1]$ 这样的区间，这样的话划分出来的区间，除了前 $k+1$ 位，剩下的肯定是 $a_i+1$ 二进制的一个前缀，所以除了前 $k+1$ 位的异或和是可以直接得到的，而前 $k$ 位也是确定的，只需要考虑第 $k+1$ 位，发现这是一个类似异或卷积的东西，直接用线段树维护即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=1e5+10;
const int p=998244353;
const ll inv=p+1>>1;
struct Node{
	int l,r,k;
};
vector<Node> vec[N];
int a[N],bit=1,now;
void getd(rint x){
	vec[x].clear();
	for(rint i=30,now=0;~i;i--)
		if(a[x]>>i&1)vec[x].push_back((Node){now,now+(1<<i)-1,i}),now+=1<<i;
	reverse(vec[x].begin(),vec[x].end());
}
int dp1[N<<2][32][2],dp2[N<<2][32][2],sum[N<<2],dp[32][2],_dp[32][2];
void upd(rint x){
	sum[bit+x]=a[x];
	getd(x);
	rll s=0;
	for(rint i=0,j=0;i<=30;i++){
		dp1[bit+x][i][0]=dp1[bit+x][i][1]=0;
		dp2[bit+x][i][0]=dp2[bit+x][i][1]=0;
		while(j<vec[x].size()&&vec[x][j].k<i)s+=vec[x][j].r-vec[x][j].l+1,j++;
		dp1[bit+x][i][a[x]>>i&1]=s%p;
		dp2[bit+x][i][a[x]>>i&1]=s%p;
		if(j<vec[x].size()&&vec[x][j].k==i){
			s+=vec[x][j].r-vec[x][j].l+1;
			dp1[bit+x][i][0]=(dp1[bit+x][i][0]+vec[x][j].r-vec[x][j].l+1)%p;
			j++;
		}
		rll d0=dp1[bit+x][i][0],d1=dp1[bit+x][i][1];
		dp1[bit+x][i][0]=(d0+d1)%p;
		dp1[bit+x][i][1]=(d0+p-d1)%p;
		d0=dp2[bit+x][i][0],d1=dp2[bit+x][i][1];
		dp2[bit+x][i][0]=(d0+d1)%p;
		dp2[bit+x][i][1]=(d0+p-d1)%p;
	}
}
void up(rint x){
	sum[x]=sum[x<<1]^sum[x<<1|1];
	for(rint i=0;i<=30;i++){
		dp1[x][i][0]=1ll*dp1[x<<1][i][0]*dp1[x<<1|1][i][0]%p;
		dp1[x][i][1]=1ll*dp1[x<<1][i][1]*dp1[x<<1|1][i][1]%p;
		dp2[x][i][0]=1ll*dp2[x<<1][i][0]*dp2[x<<1|1][i][0]%p;
		dp2[x][i][1]=1ll*dp2[x<<1][i][1]*dp2[x<<1|1][i][1]%p;
	}
}
void build(rint n){
	for(;bit<=n;bit<<=1);
	for(rint i=1;i<=n;i++)upd(i);
	for(rint i=bit-1;i;i--)up(i);
}
void update(rint x,rint v){for(a[x]=v,upd(x),x+=bit,x>>=1;x;x>>=1)up(x);}
void query(rint l,rint r){
	for(l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){
		if(~l&1){
			now^=sum[l^1];
			for(rint i=0;i<=30;i++){
				dp[i][0]=1ll*dp[i][0]*dp1[l^1][i][0]%p;
				dp[i][1]=1ll*dp[i][1]*dp1[l^1][i][1]%p;
				_dp[i][0]=1ll*_dp[i][0]*dp2[l^1][i][0]%p;
				_dp[i][1]=1ll*_dp[i][1]*dp2[l^1][i][1]%p;
			}
		}
		if(r&1){
			now^=sum[r^1];
			for(rint i=0;i<=30;i++){
				dp[i][0]=1ll*dp[i][0]*dp1[r^1][i][0]%p;
				dp[i][1]=1ll*dp[i][1]*dp1[r^1][i][1]%p;
				_dp[i][0]=1ll*_dp[i][0]*dp2[r^1][i][0]%p;
				_dp[i][1]=1ll*_dp[i][1]*dp2[r^1][i][1]%p;
			}
		}
	}
	for(rint i=0;i<=30;i++){
		rint d0=dp[i][0],d1=dp[i][1];
		dp[i][0]=(d0+d1)*inv%p;
		dp[i][1]=(d0-d1+p)*inv%p;
		d0=_dp[i][0],d1=_dp[i][1];
		_dp[i][0]=(d0+d1)*inv%p;
		_dp[i][1]=(d0-d1+p)*inv%p;
	}
}
int main(){
	rint n,m;
	scanf("%d%d",&n,&m);
	for(rint i=1;i<=n;i++)
		scanf("%d",&a[i]),a[i]++;
	build(n);
	while(m--){
		rint opt,l,r;
		scanf("%d%d%d",&opt,&l,&r);
		if(opt==1){
			update(l,r+1);
		}else {
			rint L,R;
			scanf("%d%d",&L,&R);
			now=0;
			for(rint i=0;i<=30;i++)
				dp[i][0]=_dp[i][0]=dp[i][1]=_dp[i][1]=1;
			query(l,r);
			rll res=0;
			for(rint s=0,pw=1;s<=30;s++,pw=pw*inv%p){
				rint t=now;
				now>>=s+1;now<<=s+1;
				rll len1=min(R,now|((1<<s)-1))-max(L,now)+1,len2=min(R,now|((1<<s+1)-1))-max(L,now|(1<<s))+1;
				if(len1>0)res+=(dp[s][0]-_dp[s][0])*len1%p*pw%p;
				if(len2>0)res+=(dp[s][1]-_dp[s][1])*len2%p*pw%p;
				now=t;
			}
			res=(res%p+p)%p;
			printf("%lld\n",res);
		}
	}
	return 0;
}

树

题面略长。

首先发现 $A$ ， $B$ 不喜欢的正好相反，并且互为补集，所以可以把 $A$ 不喜欢的转化一下答案，设 $a_x$ 表示与 $x$ 是祖先关系并且比 $w_x$ 小的点的个数，设 $b_x$ 表示在 $x$ 的子树中并且比 $w_x$ 大的个数， $d_x$ 表示深度，如果没有权值相等的点，那么贡献是十分好算的，即 $d_x-a_x-b_x$ 。

考虑如果有权值相等的点，一个点的贡献要额外减去它祖先中和它权值一样的点，这导致我们不太好贪心，尝试证明一个点的祖先一定比它先选，设 $u$ 是 $v$ 的祖先，那么一定有 $a_v-a_u<d_v-d_u$ 和 $b_u\ge b_v$ ，所以可以得到先选祖先一定是最优的。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=5e5+10;
const int Max=5e5;
const ll INF=1e15;
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx;
void Ins(rint a,rint b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
int n,w[N],d[N],dfn[N],siz[N],tr[N],Time;
void update(rint x,rint v){
	for(;x<=Max;x+=x&-x)
		tr[x]+=v;
}
int query(rint x){
	rint res=0;
	for(;x;x&=x-1)
		res+=tr[x];
	return res;
}
int A[N],B[N],C[N];
void dfs(rint u,rint fa){
	siz[u]=1;dfn[u]=++Time;
	A[u]=query(w[u]-1);
	C[u]=query(w[u])-A[u];
	update(w[u],1);
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa)continue;
		d[v]=d[u]+1;
		dfs(v,u);
		siz[u]+=siz[v];
	}
	update(w[u],-1);
}
struct Node{
	int x,y;
	bool operator < (const Node&A)const{
		return y>A.y;
	}
}seq[N];
char buf[1<<20],*p1,*p2;
inline char gc(){return p1==p2?p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2?EOF:*p1++:*p1++;}
inline int read(){
	rint x=0;char ch=gc();
	while(ch<'0'||ch>'9')ch=gc();
	while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=gc();
	return x;
}
ll ans[N];
int q[N];
bool cmp(rint x,rint y){
	return d[x]-A[x]-B[x]-C[x]>d[y]-A[y]-B[y]-C[y];
}
int main(){
	n=read();
	for(rint i=1;i<=n;i++)
		w[i]=read();
	for(rint i=2;i<=n;i++){
		rint x=read(),y=read();
		Ins(x,y);Ins(y,x);
	}
	dfs(1,0);
	for(rint i=1;i<=n;i++)
		seq[i]=(Node){i,w[i]};
	sort(seq+1,seq+n+1);
	rll res=0;
	for(rint i=1,j=1;i<=n;i++){
		while(j<=n&&seq[j].y>seq[i].y)
			update(dfn[seq[j].x],1),j++;
		rint t=query(dfn[seq[i].x]+siz[seq[i].x]-1)-query(dfn[seq[i].x]);
		res+=A[i];B[seq[i].x]=t;
	}
	for(rint i=1;i<=n;i++)
		q[i]=i;
	sort(q+1,q+n+1,cmp);
	ans[n]=res;
	for(rint i=n,cnt=1;i;i--,cnt++){
		res+=d[q[i]]-A[q[i]]-B[q[i]]-C[q[i]];
		ans[i-1]=1ll*cnt*(cnt-1)/2+res;
	}
	for(rint i=0;i<=n;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

数学

定义一个数是好的当且进当存在三个连续数位满足单调上升，求一个前缀 $1-n$ 满足前缀中的数中好的数占比不少于 $p$ 。

给出一个结论，对于 $\frac{B}A<p$ ，每次找到一个最小的 $C$ 满足 $\frac{B+C}{A+C}\ge p$ ，一直迭代知道找到答案，迭代次数不超过 $log$ ，所以直接大力模拟即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
#define db double
const int N=110;
const int w=1e9;
struct Node{
	ll a[N];
	Node operator + (const Node&A)const{
		Node res=*this;
		res.a[0]=max(res.a[0],A.a[0]);
		rint t=0;
		for(rint i=1;i<=res.a[0];i++){
			res.a[i]+=A.a[i]+t;
			t=res.a[i]/w;
			res.a[i]%=w;
		}
		if(t)res.a[++res.a[0]]=t;
		return res;
	}
	Node operator - (const Node&A)const{
		Node res=*this;
		res.a[0]=max(res.a[0],A.a[0]);
		for(rint i=1;i<=res.a[0];i++){
			res.a[i]-=A.a[i];
			if(res.a[i]<0)res.a[i]+=w,res.a[i+1]--;
		}
		while(!res.a[res.a[0]]&&res.a[0]>1)res.a[0]--;
		return res;
	}
	Node operator * (const int&A)const{
		Node res=*this;
		rint t=0;
		for(rint i=1;i<=res.a[0];i++){
			res.a[i]=res.a[i]*A+t;
			t=res.a[i]/w;
			res.a[i]%=w;
		}
		if(t)res.a[++res.a[0]]=t;
		return res;
	}
	Node operator / (const int&A)const{
		Node res=*this;
		rll t=0;
		for(rint i=res.a[0];i;i--){
			res.a[i]+=t;
			t=(res.a[i]%A)*w;
			res.a[i]/=A;
		}
		if(t)res.a[1]++;
		while(!res.a[res.a[0]]&&res.a[0]>1)res.a[0]--;
		return res;
	}
	bool operator < (const Node&A)const{
		if(a[0]!=A.a[0])return a[0]<A.a[0];
		for(rint i=a[0];i;i--){
			if(a[i]<A.a[i])return 1;
			if(a[i]>A.a[i])return 0;
		}
		return 0;
	}
	void print(){
		printf("%lld",a[a[0]]);
		for(rint i=a[0]-1;i;i--)
			printf("%09lld",a[i]);
	}
}A,B,dp[N][10][10][2],val1,val0;
int num[N],p1,p2,tt;
bool vis[N][10][10][2];
Node dfs(rint hh,rint v1,rint v2,rint lim1,rint lim2,rint ok){
	if(!hh)return ok?val1:val0;
	if(!lim1&&!lim2&&vis[hh][v1][v2][ok])return dp[hh][v1][v2][ok];
	Node t=val0;
	rint lim=lim1?num[hh]:9;
	for(rint i=0;i<=lim;i++){
		if(lim2)t=t+dfs(hh-1,v2,i,lim1&&i==lim,v2==0,ok);
		else t=t+dfs(hh-1,v2,i,lim1&&i==lim,0,ok|(v1<v2&&v2<i));
	}
	if(!lim1&&!lim2)vis[hh][v1][v2][ok]=1,dp[hh][v1][v2][ok]=t;
	return t;
}
Node solve(Node n){
	tt=0;
	for(rint i=1;i<=n.a[0];i++){
		if(i==n.a[0]){
			while(n.a[i])
				num[++tt]=n.a[i]%10,n.a[i]/=10;
		}else {
			for(rint j=1;j<=9;j++)
				num[++tt]=n.a[i]%10,n.a[i]/=10;
		}
	}
	return dfs(tt,0,0,1,1,0);
}
int main(){
	db p;
	scanf("%lf",&p);
	p1=p*100000+0.5;p2=100000;
	A.a[0]=B.a[0]=1;A.a[1]=100;
	val0.a[0]=val1.a[0]=1;val1.a[1]=1;
	while(B*p2<A*p1){
		Node C=(A*p1-B*p2)/(p2-p1);
		A=A+C;B=solve(A);
	}
	A.print();
	return 0;
}

城市大脑

给定一张图，每条边的边权初始化为 $1$ ，一共有 $k$ 次操作，每次操作可以将一条边的边权加一，最后通过一条边的时间为 $\frac{1}w$ ，最小化从 $s1$ 到 $t1$ 和从 $s2$ 到 $t2$ 的时间总和。

首先注意到路径可以被分为两种，一种是两人都走的一种是只有一个走的，不难发现两人都走的一定是一段连续的路程，不然让一个人改走另一段一定更优，所以可以直接枚举连续的一段然后计算时间，枚举是 $N^2$ 的，考虑如何计算时间，随着分配给两人都走的路径的时间的增加，代价一定是先减后增，猜测函数单峰，事实上确实是，所以直接三分即可，不过由于路径一共是 $N^2$ 的，每次三分太慢，考虑优化，实际上对于连续路程一样的只需要跑非连续路程最短的即可，优化后三分的次数是线性的，可以直接做。

按钮

有一块可以显示 $5$ 位数字的显示屏，每次系统从 $[L,R]$ 中选出一个数字，一次操作可以是改变显示屏上的一个数和询问数字与这个数的大小关系，问最少多少次可以知道显示屏上边是多少。

有一个显然的暴力是 $dp[x][l][r]$ 表示当前显示屏的数字是 $x$ ，区间为 $[l,r]$ 时的最小花费。

这样做比较慢，注意到答案不会太大，如果忽略操作次数大概是 $log$ 的，由于改变数字有常数所以实际上会略微大一点，不过不会超过 $42$ ，而且状态中 $x$ 要么等于 $l-1$ 要么等于 $r+1$ ，所以可以定义 $dpl[x][i]$ 表示显示屏数字为 $x$ ，操作 $i$ 次，得到的最小左端点，定义 $dpr[x][i]$ 同上，现在考虑转移， $dpl[x][i]$ 可以对 $dpl[m][i-1-dis]$ 取 $\min$ 当且仅当 $dpr[m][i-1-dis]\ge x-1$ ，为了保证能够完全覆盖区间，所以要有右端点的限制，如果没有 $dis$ 那么可以直接二维数点，但是有 $dis$ 的限制就不太好做，可以考虑枚举 $dis$ 然后把一些位置变成通配符去匹配，这样就能够做二维数点了。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=1e5+10;
struct Node{
	int pos,val;
};
int dpl[46][N],dpr[46][N];
vector<Node> vec[N];
int chk(rint x,rint y){
	rint res=0;
	for(rint i=1;i<=6;i++){
		if(x%10!=y%10)res++;
		x/=10;y/=10;
	}
	return res;
}
int cnt[1<<5],val[N<<1],w[N][1<<5];
int main(){
	for(rint i=1;i<32;i++)
		cnt[i]=cnt[i>>1]+(i&1);
	memset(dpl,0x3f,sizeof(dpl));
	rint n=1e5;
	for(rint i=1;i<=n;i++){
		dpl[0][i]=i-1,dpr[0][i]=i+1;
		for(rint j=0;j<32;j++){
			rint wv=0;
			for(rint x=i,k=0;k<5;k++,x/=10){
				if(j>>k&1)wv=wv*11+10;
				else wv=wv*11+x%10;
			}
			w[i][j]=wv;
		}
	}
	dpl[0][1]=1;dpr[0][n]=n;
	for(rint c=1;c<=45;c++){
		memset(val,0,sizeof(val));
		for(rint i=1;i<=n;i++)
			vec[i].clear();
		for(rint i=1;i<=n;i++){
			for(rint j=0;j<32;j++){
				if(cnt[j]>=c)continue;
				vec[dpl[c-cnt[j]-1][i]].push_back((Node){w[i][j],dpr[c-cnt[j]-1][i]});
			}
		}
		for(Node v:vec[1])
			val[v.pos]=max(val[v.pos],v.val);
		for(rint i=1;i<=n;i++){
			for(Node v:vec[i+1])
				val[v.pos]=max(val[v.pos],v.val);
			for(rint j=0;j<32;j++){
				dpr[c][i]=max(dpr[c][i],val[w[i][j]]);
			}
		}
		memset(val,0x3f,sizeof(val));
		for(rint i=1;i<=n;i++)
			vec[i].clear();
		for(rint i=1;i<=n;i++){
			for(rint j=0;j<32;j++){
				if(cnt[j]>=c)continue;
				vec[dpr[c-cnt[j]-1][i]].push_back((Node){w[i][j],dpl[c-cnt[j]-1][i]});
			}
		}
		for(Node v:vec[n])
			val[v.pos]=min(val[v.pos],v.val);
		for(rint i=n;i;i--){
			for(Node v:vec[i-1])
				val[v.pos]=min(val[v.pos],v.val);
			for(rint j=0;j<32;j++){
				dpl[c][i]=min(dpl[c][i],val[w[i][j]]);
			}
		}
	}
	rint T;
	scanf("%d",&T);
	while(T--){
		rint L,R;
		scanf("%d%d",&L,&R);
		rint res=1e9;
		for(rint i=L;i<=R;i++){
			rint r1=0,r2=0;
			while(dpl[r1][i]>L)r1++;
			while(dpr[r2][i]<R)r2++;
			res=min(res,chk(0,i)+max(r1,r2)+1);
		}
		printf("%d\n",res);
	}
	return 0;
}

蛋糕

有 $n$ 个点，每个点有三个值域区间，找出三个整数满足所有的点至少有一个区间包含了给定点。

实际上不太好做，但是发现可以枚举两个点，然后判断剩下的那一维有没有解，剩下的那一维是对一个数取 $\max,\min$ ，这样做是 $n^3$ 的，考虑对于第一维进行线段树分治，对于第二维开一棵线段树，每个叶子节点表示当第二维取这个节点时，第三维的区间范围，发现这个线段树不太好维护，所以尝试直接在叶子节点下推所有标记，然后看起来时间复杂度比较高，不过由于有一些减枝所以可以通过。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=2e5+10;
struct Node{
	int mx[3],mn[3];
}a[N];
int q[N],tt,Max[3],rk[3][N];
vector<Node> vec[N<<2];
void insert(rint x,rint l,rint r,rint cl,rint cr,Node v){
	if(cl<=l&&r<=cr){
		vec[x].push_back(v);
		return ;
	}
	rint mid=l+r>>1;
	if(cl<=mid)insert(x<<1,l,mid,cl,cr,v);
	if(cr>mid)insert(x<<1|1,mid+1,r,cl,cr,v);
}
struct Bin{
	int pos,tag1,tag2;
}stk[N*32];
int tp,tag1[N<<2],tag2[N<<2];
void update(rint x,rint l,rint r,rint cl,rint cr,rint v1,rint v2){
	if(cl<=l&&r<=cr){
		stk[++tp]=(Bin){x,tag1[x],tag2[x]};
		tag1[x]=max(tag1[x],v1);
		tag2[x]=min(tag2[x],v2);
		return ;
	}
	rint mid=l+r>>1;
	if(cl<=mid)update(x<<1,l,mid,cl,cr,v1,v2);
	if(cr>mid)update(x<<1|1,mid+1,r,cl,cr,v1,v2);
}
void dfs2(rint x,rint l,rint r,rint cl,rint cr,rint res){
	cl=max(cl,tag1[x]);cr=min(cr,tag2[x]);
	if(cl>cr)return ;
	if(l==r){
		puts("Yes");
		printf("%d %d %d\n",rk[0][res],rk[1][l],rk[2][cl]);
		exit(0);
	}
	rint mid=l+r>>1;
	dfs2(x<<1,l,mid,cl,cr,res);
	dfs2(x<<1|1,mid+1,r,cl,cr,res);
}
void dfs(rint x,rint l,rint r){
	rint now=tp;
	for(Node v:vec[x]){
		if(v.mn[1]!=1)update(1,1,Max[1],1,v.mn[1]-1,v.mn[2],v.mx[2]);
		if(v.mx[1]!=Max[1])update(1,1,Max[1],v.mx[1]+1,Max[1],v.mn[2],v.mx[2]);
	}
	if(l==r){
		dfs2(1,1,Max[1],1,Max[2],l);
	}else {
		rint mid=l+r>>1;
		dfs(x<<1,l,mid);
		dfs(x<<1|1,mid+1,r);
	}
	while(tp!=now){
		Bin u=stk[tp--];
		tag1[u.pos]=u.tag1;
		tag2[u.pos]=u.tag2;
	}
}
int main(){
	memset(tag2,0x3f,sizeof(tag2));
	rint n;
	scanf("%d",&n);
	for(rint i=1;i<=n;i++)
		for(rint j=0;j<3;j++)
			scanf("%d%d",&a[i].mn[j],&a[i].mx[j]);
	for(rint j=0;j<3;j++){
		tt=0;
		for(rint i=1;i<=n;i++)
			q[++tt]=a[i].mn[j],q[++tt]=a[i].mx[j];
		sort(q+1,q+tt+1);
		tt=unique(q+1,q+tt+1)-q-1;
		for(rint i=1;i<=tt;i++)
			rk[j][i]=q[i];
		for(rint i=1;i<=n;i++){
			a[i].mn[j]=lower_bound(q+1,q+tt+1,a[i].mn[j])-q;
			a[i].mx[j]=lower_bound(q+1,q+tt+1,a[i].mx[j])-q;
		}
		Max[j]=tt;
	}
	for(rint i=1;i<=n;i++){
		if(a[i].mn[0]!=1)insert(1,1,Max[0],1,a[i].mn[0]-1,a[i]);
		if(a[i].mx[0]!=Max[0])insert(1,1,Max[0],a[i].mx[0]+1,Max[0],a[i]);
	}
	dfs(1,1,Max[0]);
	puts("NO");
	return 0;
}

猜猜

有 $n$ 个宝石，每个宝石有颜色和价值，支持两种操作，将某种宝石的颜色或者价值替换，从某个位置开始取宝石，最多有 $k$ 个不取，每种颜色最多取 $k$ 种。

$k\leq10$ 。

首先考虑确定了取到的右端点 $r$ ，那么怎么决策取哪个，首先需要决策的最多只有 $k$ 个，其余的都只有一种，所以对于出现一次的求和，对于其它的取最大值。

现在的问题是怎么求 $r$ 和找出不超过 $k$ 个需要决策的数，不难发现这两个可以同时进行，现在的问题是怎么找出 $k$ 个需要决策的数，令 $pre_i$ 表示 $i$ 的前一个和这个数颜色一样的数的位置，那么当且仅当 $pre_i>=l$ 的时候才有贡献，这样的数可以用线段树找到。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define rint register int
#define ll long long
#define rll register long long
int pre[N],col[N],val[N];
set<int> pos[N];
set<int>::iterator it;
int Max[N<<2];
ll sum[N<<2];
#define ls rt<<1
#define rs rt<<1|1
void up(rint rt){
	sum[rt]=sum[ls]+sum[rs];
	Max[rt]=max(Max[ls],Max[rs]);
}
void update(rint rt,rint l,rint r,rint pos,rint v1,rint v2){
	if(l==r){
		Max[rt]=v1;
		sum[rt]=v2;
		return ;
	}
	rint mid=l+r>>1;
	if(pos<=mid)update(ls,l,mid,pos,v1,v2);
	else update(rs,mid+1,r,pos,v1,v2);
	up(rt);
}
int q[N],w[N],tt,k,s;
ll query(rint rt,rint l,rint r,rint cl,rint cr){
	if(tt>k)return 0;
	if(cl<=l&&r<=cr&&Max[rt]<s)return sum[rt];
	if(l==r){
		if(Max[rt]>=s){
			q[++tt]=l;
			return 0;
		}else return sum[rt];
	}
	rint mid=l+r>>1;
	if(cr<=mid)return query(ls,l,mid,cl,cr);
	if(cl>mid)return query(rs,mid+1,r,cl,cr);
	return query(ls,l,mid,cl,cr)+query(rs,mid+1,r,cl,cr);
}
int main(){
	rint n,m;
	scanf("%d%d",&n,&m);
	for(rint i=1;i<=n;i++){
		scanf("%d%d",&col[i],&val[i]);
		if(!pos[col[i]].empty())pre[i]=*pos[col[i]].rbegin();
		update(1,1,n,i,pre[i],val[i]);
		pos[col[i]].insert(i);
	}
	while(m--){
		rint opt;
		scanf("%d",&opt);
		if(opt==1){
			rint v1,v2,v3;
			scanf("%d%d%d",&v1,&v2,&v3);
			it=pos[col[v1]].upper_bound(v1);
			if(it!=pos[col[v1]].end()){
				rint p=*it;
				if(--it!=pos[col[v1]].begin())pre[p]=*--it;
				else pre[p]=0;
				update(1,1,n,p,pre[p],val[p]);
			}
			pos[col[v1]].erase(v1);
			col[v1]=v2;val[v1]=v3;
			pos[col[v1]].insert(v1);
			it=pos[col[v1]].upper_bound(v1);
			if(it!=pos[col[v1]].end()){
				rint p=*it;
				pre[p]=v1;
				update(1,1,n,p,pre[p],val[p]);
			}
			it=pos[col[v1]].find(v1);
			if(it!=pos[col[v1]].begin())pre[v1]=*--it;
			else pre[v1]=0;
			update(1,1,n,v1,pre[v1],val[v1]);
		}else {
			scanf("%d%d",&s,&k);tt=0;
			rll res=query(1,1,n,s,n);
			if(tt>k)tt--;
			for(rint i=1;i<=tt;i++){
				rint nxt=pre[q[i]];
				if(pre[nxt]<s){
					res-=val[nxt];
					w[col[nxt]]=max(w[col[nxt]],val[nxt]);
				}
				w[col[nxt]]=max(w[col[nxt]],val[q[i]]);
			}
			for(rint i=1;i<=tt;i++)
				res+=w[col[q[i]]],w[col[q[i]]]=0;
			printf("%lld\n",res);
		}
	}
	return 0;
}

今天

给出放置每个字符的概率，每次随机放置字符，当这个字符包含给出的某个子串时就停止，求停止的期望，需要对于某个字符串的所有前缀回答。

如果是一个串的匹配可以直接用 $kmp$ ，对于多个串的话考虑 $AC$ 自动机，暴力列出转移的式子然后高斯消元不太行，不过可以用 $n$ 个特殊量来表示所有的变量，这样的话只需要对于最后的 $n$ 个点跑高斯消元即可，问题在于怎么找 $n$ 个点，事实上可以直接对 Trie 树跑随机链剖分，这样将每个链的链顶自己表示自己即可，转移的时候从父亲转移过来。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=1e4+10;
const int p=1e9+7;
char s[N];
inline ll fpow(rll a,rll b){
	rll res=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)res=res*a%p;
	return res;
}
int f[110],g[N],mt[110][110],b[110],a[N][110],ans[N];
int n,m,k,ch[N][26],cnt;
void insert(){
	rint now=0;
	for(rint i=1;i<=m;i++){
		rint x=s[i]-'a';
		if(!ch[now][x])ch[now][x]=++cnt;
		now=ch[now][x];
	}
}
int fail[N],q[N],id[N],tot,hh,tt,tot2;
void bfs(){
	hh=0;tt=-1;q[++tt]=0;id[0]=++tot;a[0][tot]=1;
	while(hh<=tt){
		rint u=q[hh++],son=0,gl=0;
		for(rint i=0;i<k;i++){
			if(ch[u][i]){
				if(u)fail[ch[u][i]]=ch[fail[u]][i];
				q[++tt]=ch[u][i];
				if(son)id[ch[u][i]]=++tot,a[ch[u][i]][tot]=1;
				else son=ch[u][i],gl=fpow(g[i],p-2);
			}else ch[u][i]=ch[fail[u]][i];
		}
		if(!son){
			b[++tot2]=(p-a[u][0])%p;
			for(rint i=1;i<=tot;i++)
				mt[tot2][i]=a[u][i];
		}else {
			for(rint i=0;i<=tot;i++)
				a[son][i]=1ll*a[u][i]*gl%p;
			a[son][0]=(a[son][0]+p-gl)%p;
			for(rint i=0;i<k;i++){
				if(ch[u][i]==son)continue;
				for(rint j=0;j<=tot;j++)
					a[son][j]=(a[son][j]+p-1ll*a[ch[u][i]][j]*gl%p*g[i]%p)%p;
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(rint i=0;i<k;i++){
		rint x;
		scanf("%d",&x);
		g[i]=x*fpow(100,p-2)%p;
	}
	for(rint i=1;i<=n;i++){
		scanf("%s",s+1);
		insert();
	}
	bfs();
	for(rint i=1;i<=tot;i++){
		if(!mt[i][i]){
			for(rint j=i;j<=tot;j++){
				if(mt[j][i]){
					for(rint z=1;z<=tot;z++)
						swap(mt[i][z],mt[j][z]);
					swap(b[i],b[j]);
				}
			}
		}
		for(rint j=1;j<=tot;j++){
			if(!mt[j][i]||i==j)continue;
			ll r=1ll*mt[j][i]*fpow(mt[i][i],p-2)%p;
			for(rint z=i;z<=tot;z++)
				mt[j][z]=(mt[j][z]-mt[i][z]*r%p+p)%p;
			b[j]=(b[j]-b[i]*r%p+p)%p;
		}
	}
	for(rint i=1;i<=tot;i++)
		b[i]=b[i]*fpow(mt[i][i],p-2)%p;
	for(rint i=0;i<=cnt;i++){
		ans[i]=a[i][0];
		for(rint j=1;j<=tot;j++)
			ans[i]+=1ll*a[i][j]*b[j]%p;
		ans[i]%=p;
	}
	scanf("%s",s+1);
	rint now=0;m=strlen(s+1);
	for(rint i=1;i<=m;i++){
		now=ch[now][s[i]-'a'];
		printf("%d\n",(ans[now]+i)%p);
	}
	return 0;
}

是谁

验证冰雹猜想。

由于冰雹猜想一个数的操作次数不会很多，所以直接模拟就行了。

考虑如何快速模拟这个过程，首先不难想到压位，有一个 $O(ans\frac{n}w)$ 的做法，显然是过不去的，这个东西时间复杂度比较高的原因在于进位的次数比较多，考虑优化掉进位的次数，没有必要每一次操作都进位，实际上可以在处理完一块后统一进位，这样做的时间复杂度是 $O(ans+(\frac{n}w)^2)$ 的，可以通过。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=3e7+10;
const int w=19;
const int B=1<<w;
char s[N];
ll a[N],k2[B],b2[B],r[B];
inline void solve(rll x){
	rll t=x,k=1,b=0,res=0,bas=1;
	while(bas<B){
		if(x%(bas<<1)==0)bas<<=1;
		else x=x*3+bas,k=k*3,b=b*3+bas;
		res++;
	}
	k2[t]=k;b2[t]=b;r[t]=res;
	return ;
}
inline ll solve2(rll x){
	rll res=0;
	while(x!=1){
		if(x&1)x=x*3+1;
		else x>>=1;
		res++;
	}
	return res;
}
int main(){
	scanf("%s",s+1);
	rint n=strlen(s+1);
	reverse(s+1,s+n+1);
	for(rint i=1;i<=n;i+=w)
		for(rint j=0;j<w&&i+j<=n;j++)
			a[i/w+1]|=(s[i+j]-'0')<<j;
	for(rint i=0;i<B;i++)
		solve(i);
	n=(n-1)/w+1;
	rll res=0;
	for(rint i=1;i<=n;i++){
		if(i==n)res+=solve2(a[i]);
		else {
			res+=r[a[i]];
			rll t=a[i];
			for(rint j=i;j<=n;j++)
				a[j]*=k2[t];
			a[i]+=b2[t];t=0;
			for(rint j=i;j<=n;j++)
				a[j]+=t,t=a[j]>>w,a[j]&=B-1;
			if(t)n++,a[n]=t;
		}
	}
	printf("%lld\n",res);
	return 0;
}

简单题

维护一个数组 $a$ ，给定 $[l,r]$ 和 $v$ ，对于区间内的每个 $a_i$ ，支持两种操作

$a_i=v$

$b[a_i]+=v$

发现可以简单分块维护，如果一个块有赋值标记那么直接加到标记上，否则新开一个。

进一步发现如果只维护这两个操作那么实际上没有必要用分块，线段树就行了，标记的处理同理，注意如果一个节点同时有赋值和加法，那么加法一定是给下面的节点，因为上面传来的加法都加在了赋值上。

上述做法是数据结构写傻了的类型，考虑时光倒流，那么每次赋值操作相当于取走一段区间的数然后加上来，所以只需要写区间加和区间清空。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=5e5+10;
inline int read(){
	rint x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
#define ls rt<<1
#define rs rt<<1|1
int tag[N<<2];
ll tag2[N<<2],b[N<<2];
void Build(rint rt,rint l,rint r){
	tag[rt]=-1;
	if(l==r){
		tag[rt]=read();
		return ;
	}
	rint mid=l+r>>1;
	Build(ls,l,mid);
	Build(rs,mid+1,r);
}
void down(rint rt,rint l,rint r){
	rint mid=l+r>>1;
	if(tag2[rt]){
		if(tag[ls]!=-1)b[tag[ls]]+=tag2[rt]*(mid-l+1);
		else tag2[ls]+=tag2[rt];
		if(tag[rs]!=-1)b[tag[rs]]+=tag2[rt]*(r-mid);
		else tag2[rs]+=tag2[rt];
		tag2[rt]=0;
	}
	if(tag[rt]!=-1){
		tag[ls]=tag[rs]=tag[rt];
		tag[rt]=-1;
	}
}
void modify(rint rt,rint l,rint r,rint cl,rint cr,rint v){
	if(cl<=l&&r<=cr){
		tag[rt]=v;
		return ;
	}
	down(rt,l,r);
	rint mid=l+r>>1;
	if(cl<=mid)modify(ls,l,mid,cl,cr,v);
	if(cr>mid)modify(rs,mid+1,r,cl,cr,v);
}
void update(rint rt,rint l,rint r,rint cl,rint cr,rll v){
	if(cl<=l&&r<=cr){
		if(tag[rt]!=-1)b[tag[rt]]+=v*(r-l+1);
		else tag2[rt]+=v;
		return ;
	}
	down(rt,l,r);
	rint mid=l+r>>1;
	if(cl<=mid)update(ls,l,mid,cl,cr,v);
	if(cr>mid)update(rs,mid+1,r,cl,cr,v);
}
void dfs(rint rt,rint l,rint r){
	if(l==r)return ;
	down(rt,l,r);
	rint mid=l+r>>1;
	dfs(ls,l,mid);dfs(rs,mid+1,r);
}
int main(){
	rint n=read(),m=read(),q=read();
	Build(1,1,n);
	while(q--){
		rint opt=read(),l=read(),r=read(),v=read();
		if(opt==1)
			modify(1,1,n,l,r,v);
		else 
			update(1,1,n,l,r,v);
	}
	dfs(1,1,n);
	for(rint i=1;i<=m;i++)
		printf("%lld\n",b[i]);
	return 0;
}

树上游走

在树上从 $S$ 开始随机游走，每次等概率向外走一条边，一个点走出去两次之后就消失了，问最后停在每个点的概率。

首先分析一下一次游走的性质，显然最后只会停在度数为二的节点或者度数为一的 $S$ 节点或者叶子节点，所以只在度数不超过二的时候停机答案，假如以 $S$ 为根做 $dfs$ ，那么走到一个点时，如果它作为最后一个点，那么它的父亲必须要在走下来时消失，不然再次走上去这个点的子树走不完，而如果不作为最后的点，它的父亲是可以存在的，而父亲的存在与否是会影响到下一步的概率，所以需要维护一个 $dp[u][0/1]$ 表示走到 $u$ ，它的父亲在不在的概率，然后进一步发现，父亲消失了就需要走儿子，因为儿子必须消失所以至少要走两步，走一步的时候这个儿子是存在的，这个也是会影响下一步的概率的，所以维护一个 $sp$ 数组，表示这个点向下走一步的概率，这个是非常好维护的，还有一个 $f$ 数组，表示向下走至少两步的概率，维护出来之后随便转移一下即可。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
#define ull unsigned long long
const int N=1e5+10;
const int p=998244353;
ll fpow(rll a,rll b){
	rll res=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)res=res*a%p;
	return res;
}
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx;
void Ins(rint a,rint b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
int n,s,w[N],du[N];
ll d1[N],d2[N];
ll f[N][2],g[N],dp[N][2],sp[N][2];
void dfs(rint u,rint fa){
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa)continue;
		dfs(v,u);
		sp[u][0]=(sp[u][0]+d2[u]*d1[v])%p;
		f[u][0]=(f[u][0]+f[v][1]*d2[u]%p*d2[v]+sp[v][1]*d2[u]%p*d1[v])%p;
		sp[u][1]=(sp[u][1]+d1[u]*d1[v])%p;
		f[u][1]=(f[u][1]+f[v][1]*d1[u]%p*d2[v]+sp[v][1]*d1[u]%p*d1[v])%p;
	}
}
void dfs2(rint u,rint fa,rll lstp){
	if(du[u]==2)
		g[u]=dp[u][0]*f[u][0]%p;
	if(du[u]==1){
		g[u]=(dp[u][0]+lstp)%p;
	}
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(v==fa)continue;
		sp[u][0]-=d2[u]*d1[v]%p;sp[u][0]=(sp[u][0]+p)%p;
		sp[u][1]-=d1[u]*d1[v]%p;sp[u][1]=(sp[u][1]+p)%p;
		f[u][0]-=f[v][1]*d2[u]%p*d2[v]%p+sp[v][1]*d2[u]%p*d1[v]%p;f[u][0]=(f[u][0]%p+p)%p;
		f[u][1]-=f[v][1]*d1[u]%p*d2[v]%p+sp[v][1]*d1[u]%p*d1[v]%p;f[u][1]=(f[u][1]%p+p)%p;
		dp[v][0]=(dp[u][0]*f[u][0]%p*fpow(du[u]-2,p-2)%p+dp[u][0]*sp[u][0]%p*d2[u]%p+
				lstp*d2[u]%p+dp[u][1]*f[u][1]%p*d2[u]%p+dp[u][1]*sp[u][1]%p*d1[u])%p;
		dp[v][1]=(dp[u][0]*d2[u]+dp[u][1]*d1[u])%p;
		dfs2(v,u,(dp[u][0]*d2[u]%p*d1[v]%p*d2[u]%p+dp[u][1]*d1[u]%p*d1[v]%p*d1[u]%p)%p);
		sp[u][0]+=d2[u]*d1[v]%p;sp[u][0]=(sp[u][0]+p)%p;
		sp[u][1]+=d1[u]*d1[v]%p;sp[u][1]=(sp[u][1]+p)%p;
		f[u][0]+=f[v][1]*d2[u]%p*d2[v]%p+sp[v][1]*d2[u]%p*d1[v]%p;f[u][0]=(f[u][0]%p+p)%p;
		f[u][1]+=f[v][1]*d1[u]%p*d2[v]%p+sp[v][1]*d1[u]%p*d1[v]%p;f[u][1]=(f[u][1]%p+p)%p;
	}
}
void solve(){
	dfs(s,0);
	dp[s][0]=1;
	for(rint i=h[s];i;i=e[i].nxt){
		rint v=e[i].to;
		sp[s][1]-=d1[s]*d1[v]%p;sp[s][1]=(sp[s][1]+p)%p;
		f[s][1]-=f[v][1]*d1[s]%p*d2[v]%p+sp[v][1]*d1[s]%p*d1[v]%p;f[s][1]=(f[s][1]%p+p)%p;
		dp[v][0]=(dp[s][0]*f[s][1]%p*d2[s]%p+dp[s][0]*sp[s][1]%p*d1[s]%p)%p;
		dp[v][1]=(dp[s][0]*d1[s])%p;
		dfs2(v,s,d1[v]*d1[s]%p*d1[s]%p);
		sp[s][1]+=d1[s]*d1[v]%p;sp[s][1]=(sp[s][1]+p)%p;
		f[s][1]+=f[v][1]*d1[s]%p*d2[v]%p+sp[v][1]*d1[s]%p*d1[v]%p;f[s][1]=(f[s][1]%p+p)%p;
	}
	if(du[s]==1)g[s]=f[s][1];
	else g[s]=0;
	rll res=0;
	for(rint i=1;i<=n;i++)
		res+=g[i]*w[i]%p;
	printf("%lld\n",res%p);
}
int main(){
	scanf("%d%d",&n,&s);
	for(rint i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for(rint i=2;i<=n;i++){
		rint x,y;
		scanf("%d%d",&x,&y);
		Ins(x,y);Ins(y,x);
		du[x]++;du[y]++;
	}
	for(rint i=1;i<=n;i++)
		d2[i]=fpow(du[i]-1,p-2),d1[i]=fpow(du[i],p-2);
	solve();
	return 0;
}

树的同构

给定一棵树，找到两个没有交的联通块使得存在一种重新标号的方式让这两个联通块形状一样。

$n\leq50$

首先可以枚举一个联通子集然后用树哈希判断。

其次不难想到枚举两个点，钦定这两个点必选，然后剩下的事就是一步一步向外扩展，这个扩展是很不好做的，考虑定义一个数组 $F[x][y]$ 表示在同构中， $x$ 对应 $y$ ，这样得到的点集最大是多少，这样的话就转移是一个类似二分图最大带权匹配的东西，用费用流就行了。

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define rll register long long
const int N=55;
struct Edge{
	int to,nxt;
}e[N<<1];
int h[N],idx,x[N],y[N];
void Ins(rint a,rint b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
namespace Netflow{
	struct Edge{
		int to,nxt,cost,val;
	}e[N*N*2];
	int h[N],idx;
	void Ins(rint a,rint b,rint c,rint d){
		e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
		e[idx].val=c;e[idx].cost=d;
	}
	int mp[N],cnt,st,ed;
	void clear(){
		st=1;ed=2;cnt=2;idx=1;
		memset(h,0,sizeof(h));
	}
	int pre[N],dis[N];
	bool vis[N];
	queue<int> q;
	bool spfa(){
		memset(dis,-0x3f,sizeof(dis));
		q.push(st);dis[st]=0;
		while(!q.empty()){
			rint u=q.front();q.pop();vis[u]=0;
			for(rint i=h[u];i;i=e[i].nxt){
				rint v=e[i].to;
				if(e[i].val&&dis[v]<dis[u]+e[i].cost){
					dis[v]=dis[u]+e[i].cost;
					pre[v]=i;
					if(!vis[v]){
						q.push(v);
						vis[v]=1;
					}
				}
			}
		}
		return dis[ed]!=dis[0];
	}
	int getans(){
		rint res=0;
		while(spfa()){
			rint Min=1e9;
			for(rint now=ed;now!=st;now=e[pre[now]^1].to)
				Min=min(Min,e[pre[now]].val);
			for(rint now=ed;now!=st;now=e[pre[now]^1].to)
				e[pre[now]].val-=Min,e[pre[now]^1].val+=Min;
			res+=Min*dis[ed];
		}
		return res;
	}
};
char s[10005];
int readIn(){
	cin.getline(s+1,10000);
	rint len=strlen(s+1),n=0;
	for(rint i=1,v=0;i<=len;i++){
		if(s[i]==' '){
			x[++n]=v;
			v=0;
		}else if(s[i]<='9'&&s[i]>='0')
			v=v*10+s[i]-'0';
	}
	cin.getline(s+1,10000);
	len=strlen(s+1);n=0;
	for(rint i=1,v=0;i<=len;i++){
		if(s[i]==' '){
			y[++n]=v;
			v=0;
		}else if(s[i]<='9'&&s[i]>='0')
			v=v*10+s[i]-'0';
	}
	for(rint i=1;i<=n;i++)
		Ins(x[i]+1,y[i]+1),Ins(y[i]+1,x[i]+1);
	return n+1;
}
bool vis[N];
int Maxd,f[N][N];
vector<int> vec1[N],vec2[N],g[N];
void dfs(rint u,rint d,vector<int> vec[]){
	vis[u]=1;Maxd=max(Maxd,d);vec[d].push_back(u);g[u].clear();
	for(rint i=h[u];i;i=e[i].nxt){
		rint v=e[i].to;
		if(vis[v])continue;
		g[u].push_back(v);
		dfs(v,d+1,vec);
	}
}
int main(){
	rint n=readIn(),res=0,cnt=0;
	for(rint x=1;x<=n;x++)
	for(rint y=1;y<=n;y++){
		if(x==y)continue;
		memset(f,0,sizeof(f));
		memset(vis,0,sizeof(vis));
		Maxd=0;vis[y]=1;
		dfs(x,1,vec1);
		dfs(y,1,vec2);
		for(rint v1:vec1[Maxd])for(rint v2:vec2[Maxd])
			f[v1][v2]=f[v2][v1]=1;
		for(rint d=Maxd-1;d;d--){
			for(rint v1:vec1[d])for(rint v2:vec2[d]){
				Netflow::clear();
				for(rint s1:g[v1]){
					Netflow::mp[s1]=++Netflow::cnt;
					Netflow::Ins(Netflow::st,Netflow::cnt,1,0);
					Netflow::Ins(Netflow::cnt,Netflow::st,0,0);
				}
				for(rint s2:g[v2]){
					Netflow::mp[s2]=++Netflow::cnt;
					Netflow::Ins(Netflow::cnt,Netflow::ed,1,0);
					Netflow::Ins(Netflow::ed,Netflow::cnt,0,0);
				}
				for(rint s1:g[v1])for(rint s2:g[v2]){
					Netflow::Ins(Netflow::mp[s1],Netflow::mp[s2],1,f[s1][s2]);
					Netflow::Ins(Netflow::mp[s2],Netflow::mp[s1],0,-f[s1][s2]);
				}
				f[v1][v2]=f[v2][v1]=Netflow::getans()+1;
			}
		}
		for(rint d=1;d<=Maxd;d++)
			vec1[d].clear(),vec2[d].clear();
		res=max(res,f[x][y]);
	}
	printf("%d\n",res);
	return 0;
}

杂题

#杂题

杂题选做

https://suzipei.github.io/2023/01/10/problem1/

作者

Su_Zipei

发布于

2023年1月10日

许可协议

微积分复习上一篇

python笔记下一篇