专题题解 - XR-3

本场比赛平均质量较高，比 XR-4 更好一些。

---

A. 等差数列

难度：$\bigstar$

题目大意：

求首项为 $a_1$，第二项为 $a_2$ 的 $n$ 项等差数列元素和。

$|a_1|,|a_2|,n\leq 10^6$

题目解法：

答案为 $\binom n 2\times (a_2-a_1)+na_1$，时间复杂度 $O(1)$。

这样的题目出现在比赛中是怎么会事呢？

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c;
int main () {
	scanf("%lld%lld%lld",&a,&b,&c);
	printf("%lld\n",(b-a)*(c*(c-1)/2)+a*c);
	return 0;
}

---

B. 小道消息

难度：$\bigstar$

题目大意：

有 $n$ 个人，代号为 $2,\ldots,n+1$，第零秒将一个信息告诉第 $k$ 个人，每秒内，知道消息的人会将消息告诉所有代号和他的代号互素的人，问至少多少秒后所有人都知道了信息。

$2\leq n\leq 10^{14}$

题目解法：

众所周知 $(n,2n]$ 中有至少一个素数，所以答案至多是 $2$，只需要判定答案是不是 $1$，即 $k+1$ 是否与所有其他数互素。

时间复杂度为 $O(\sqrt n)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k;
int main () {
	scanf("%lld%lld",&n,&k);
	n++,k++;
	for (ll i=2;i*i<=k;i++) {
		if (k%i==0) {
			printf("2\n");
			return 0;
		}
	}
	if (k*2<=n) {printf("2\n");}
	else {printf("1\n");}
	return 0;
}

---

C. 核心城市

难度：$\bigstar$

题目大意：

给定 $n$ 个点的树，你可以选择包含 $k$ 个点的一个连通块，最小化所有点到连通块的最短距离的最大值，只需要输出这个最小的最大值。

$n\leq 10^5$

题目解法：

二分答案 $C$，考虑枚举连通块的 LCA，LCA 之下只要是到子树内最远点距离不小于 $C$ 的点就要选，直接进行一个换根 DP 就可以了。

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

事实上也可以先证明直径中点必选，然后直接排序选择，可以 $O(n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,k,x,y,ans,f[MAXN],bel[MAXN],g[MAXN],h[MAXN],dp[MAXN];
vector <int> v[MAXN];
void dfs1 (int x,int fa) {
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		if (v[x][i]==fa) {continue;}
		dfs1(v[x][i],x);
		if (f[v[x][i]]+1>f[x]) {
			g[x]=f[x];
			bel[x]=v[x][i],f[x]=f[v[x][i]]+1;
		} else if (f[v[x][i]]+1>g[x]) {
			g[x]=f[v[x][i]]+1;
		}
	}
	return;
}
void dfs2 (int x,int fa) {
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		if (v[x][i]==fa) {continue;}
		if (v[x][i]==bel[x]) {h[v[x][i]]=max(h[x],g[x])+1;}
		else {h[v[x][i]]=max(h[x],f[x])+1;}
		dfs2(v[x][i],x);
	}
	return;
}
void dfs3 (int x,int fa,int vv) {
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		if (v[x][i]==fa) {continue;}
		dfs3(v[x][i],x,vv);
		dp[x]+=dp[v[x][i]];
	}
	if (f[x]>=vv) {dp[x]++;}
	if (h[x]<=vv) {ans=min(ans,dp[x]);}
}
bool chk (int x) {
	memset(dp,0,sizeof(dp));
	ans=1e9;
	dfs3(1,0,x);
	return (ans<=k);
}
int main () {
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n-1;i++) {
		scanf("%d%d",&x,&y);
		v[x].push_back(y),v[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1,0);
	int l=1,r=n;
	while (l<r) {
		int mid=(l+r)>>1;
		if (chk(mid)) {r=mid;}
		else {l=mid+1;}
	}
	printf("%d\n",l);
	return 0;
}

---

D. 系统设计

难度：$\bigstar\bigstar$（更优复杂度 $\bigstar\bigstar\bigstar$）

题目大意：

给定 $n$ 个点的有根树，长度为 $m$ 的序列 $a_1,\ldots,a_m$，支持 $q$ 个操作：

• 修改操作：序列的单点修改；
• 查询操作：给定 $x,l,r$，求从 $x$ 出发，依次考虑 $i=a_l,\ldots,a_r$，如果 $x$ 有大于 $i$ 个儿子就令 $x$ 变为其编号第 $i$ 小的儿子，否则终止过程，问过程结束后 $x$ 到了哪里。

$1\leq n,m,q\leq 5\times 10^5$

题目解法：

考虑重链剖分，查询时先快速跳掉在重链上下行的部分，然后走一条轻边，由于轻边最多只会走 $\log n$ 次，所以只需要快速求出在一条重链上能走多远，而这只需要预处理重链上每个点重儿子编号相对大小构成的序列的区间 Hash 值，与序列 $a$ 的区间 Hash 值比对即可。

具体地，由于存在修改，可以用线段树维护 $a$ 的区间 Hash，查询时直接二分则总复杂度为 $O(n\log^3 n)$，如果线段树上二分则总复杂度为 $O(n\log^2 n)$。

然而还有一种更好的做法，首先我们可以“回退”根结点到 $x$ 的这一段（视为在 $a_l,\ldots,a_r$ 这个序列前加入一些数），将问题转化为从根结点出发，那么只需要预先存好每个点对应的从根结点出发的路径的 Hash 值，就只要查询最大的 $m$ 使得 $a_l,\ldots,a_m$ 的 Hash 值与某个点的 Hash 值匹配，采用线段树上二分，复杂度为 $O(n\log n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=500010,B=10000017,P=998244353;
int n,m,q,rt,op,x,y,z,a[MAXN],tp[MAXN],dep[MAXN],siz[MAXN],wsn[MAXN],wsnx[MAXN];
int pw[MAXN],val[MAXN<<2];
vector <int> sn[MAXN],hs[MAXN],poi[MAXN];
void dfs1 (int x,int fa) {
	siz[x]=1,dep[x]=dep[fa]+1;
	int len=sn[x].size();
	for (int i=0;i<len;i++) {
		dfs1(sn[x][i],x);
		siz[x]+=siz[sn[x][i]];
		if (!wsn[x]||siz[wsn[x]]<siz[sn[x][i]]) {wsn[x]=sn[x][i],wsnx[x]=i+1;}
	}
	return;
}
void dfs2 (int x,int fa) {
	int len=sn[x].size();
	for (int i=0;i<len;i++) {
		if (sn[x][i]==wsn[x]) {tp[sn[x][i]]=tp[x];}
		else {tp[sn[x][i]]=sn[x][i];}
		dfs2(sn[x][i],x);
	}
	if (tp[x]==x) {
		int tmp=x,cnt=0;
		hs[x].push_back(0);
		while (tmp) {
			if (wsn[tmp]) {hs[x].push_back((1ll*hs[x][cnt]*B+wsnx[tmp])%P);}
			poi[x].push_back(tmp);
			tmp=wsn[tmp],cnt++;
		}
	}
	return;
}
void buildt (int p,int l,int r) {
	if (l==r) {val[p]=a[l];return;}
	int mid=(l+r)>>1;
	buildt(p<<1,l,mid);
	buildt((p<<1)|1,mid+1,r);
	val[p]=(1ll*val[p<<1]*pw[r-mid]+val[(p<<1)|1])%P;
	return;
}
void modify (int p,int l,int r,int pos,int v) {
	if (l==r) {val[p]=v;return;}
	int mid=(l+r)>>1;
	if (pos<=mid) {modify(p<<1,l,mid,pos,v);}
	else {modify((p<<1)|1,mid+1,r,pos,v);}
	val[p]=(1ll*val[p<<1]*pw[r-mid]+val[(p<<1)|1])%P;
}
int query (int p,int l,int r,int xl,int xr) {
	if (xr<l||r<xl) {return 0;}
	if (xl<=l&&r<=xr) {return val[p];}
	int mid=(l+r)>>1;
	if (xr<=mid) {return query(p<<1,l,mid,xl,xr);}
	return (1ll*query(p<<1,l,mid,xl,xr)*pw[min(xr,r)-mid]+query((p<<1)|1,mid+1,r,xl,xr))%P; 
}
int main () {
	scanf("%d%d%d",&n,&m,&q);
	pw[0]=1;
	for (int i=1;i<=m;i++) {pw[i]=(1ll*pw[i-1]*B)%P;}
	for (int i=1;i<=n;i++) {
		scanf("%d",&x);
		if (x==0) {rt=i;}
		else {sn[x].push_back(i);}
	}
	for (int i=1;i<=n;i++) {sort(sn[i].begin(),sn[i].end());}
	dfs1(rt,0);
	tp[rt]=rt;
	dfs2(rt,0);
	for (int i=1;i<=m;i++) {scanf("%d",&a[i]);}
	buildt(1,1,m);
	for (int i=1;i<=q;i++) {
		scanf("%d",&op);
		if (op==1) {
			scanf("%d%d%d",&x,&y,&z);
			while (1) {
				if (wsnx[x]!=a[y]||y>z) {
					if (sn[x].size()<a[y]||y>z) {break;}
					x=sn[x][a[y]-1];
					y++;
					continue;
				}
				int fx=tp[x];
				int l=1,r=poi[fx].size()-1-(dep[x]-dep[fx]);
				r=min(z-y+1,r);
				while (l<r) {
					int mid=(l+r+1)>>1;
					int tmpa=(1ll*hs[fx][dep[x]-dep[fx]]*pw[mid]+
					query(1,1,m,y,y+mid-1))%P,tmpb=hs[fx][dep[x]-dep[fx]+mid];
					if (tmpa==tmpb) {l=mid;}
					else {r=mid-1;}
				}
				y+=l,x=poi[fx][dep[x]-dep[fx]+l];
			}
			printf("%d\n",x);
		} else {
			scanf("%d%d",&x,&y);
			modify(1,1,m,x,y);
			a[x]=y;
		}
	}
	return 0;
}

---

E. Namid[A]me

难度：$\bigstar\bigstar\bigstar$

题目大意：

给定 $n$ 个点的点带权树，设其叶子（度数为 $1$ 的点）个数为 $d$，点 $i$ 的权值为 $a_i$，令 $f(u,v)$ 为 $u\to v$ 路径上点权与，对所有无序对 $(u,v)$ 求和 $f(u,v)^{f(u,v)}$，答案对 $786433$ 取模，模数有一个原根是 $10$。

$1\leq n\leq 2\times 10^5, a_i<2^{30}, 1\leq n\times d\leq 3\times 10^6$

题目解法：

我的做法似乎和题解不太一样。

显然树中的任意一条路径是以某个叶子为根时的一段祖先链，我们不妨依次枚举叶子 $l_1,\ldots,l_d$ 为根，统计祖先链的贡献。

对于确定的 $u$，枚举其祖先 $v$ 的过程中，显然 $f(u,v)$ 只有不超过 $\log A$ 种取值（$A$ 是 $a_i$ 的上界），并且在 DFS 过程中对每一位记录最深的这一位为 $0$ 的点就可以得到这 $\log A$ 种值和它们的分界点，于是只需要 $O(n\log A)$ 就可以统计所有祖先链的答案。

但是这样会重复计算，所以我们不妨让 $l_i$ 为根时不再计算在 $l_1,\ldots,l_{i-1}$ 为根时已经计算过的那些路径。

设祖先链是 $u\to v$（$v$ 是祖先，$u$ 是后代），再设 $w$ 是 $v$ 到 $u$ 路径上 $v$ 的后继点，那么这条祖先链之前没有被算过，当且仅当 $l_1,\ldots,l_{i-1}$ 都在 $w$ 的子树中，且都不在 $u$ 的子树中，也就是说我们只是对 $u$ 的选取进行限制，然后再限制 $v$ 是 $u$ 的深度不超过一个定值的祖先，还是可以用与上面相同的 DFS 方法求解。

注意利用原根使得幂的计算变为 $O(1)$ 的。

时间复杂度为 $O(dn\log A)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010,P=786433;
int n,x,y,cnt,nw,ans,lf[MAXN],a[MAXN],b[MAXN],dp[MAXN];
int lg[P+10],ex[P+10],f[MAXN],dep[MAXN],srt[MAXN];
pair <int,int> las[MAXN][32];
vector <int> v[MAXN];
bool cmp (pair <int,int> a,pair<int,int> b) {return a.first>b.first;}
int calc (int x) {
	if (x%P==0) {return 0;}
	return ex[(1ll*x*lg[x%P])%(P-1)];
}
void gt (int a,int b) {
	//cout << "    " << a << "  " << b << "  ";
	int tmp=dep[b];
	if (!srt[b]) {
		sort(las[b],las[b]+30,cmp);
		srt[b]=1;
	}
	for (int i=0;i<30;i++) {
		ans=(ans+(1ll*calc(a)*(tmp-las[b][i].first))%P)%P;
		tmp=las[b][i].first;
		if (a&(1<<las[b][i].second)) {a^=(1<<las[b][i].second);}
	}
	//cout << ans << endl;
	return;
}
void dfs1 (int x,int fa) {
	dp[x]=b[x],f[x]=fa,dep[x]=dep[fa]+1,srt[x]=0;
	for (int i=0;i<30;i++) {
		las[x][i]=las[fa][i];
		if (!(a[x]&(1<<i))) {las[x][i]=make_pair(dep[x],i);}
	}
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		if (v[x][i]==fa) {continue;}
		dfs1(v[x][i],x);
		dp[x]+=dp[v[x][i]];
	}
	return;
}
void dfs2 (int x,int dep,int mdep,int nwv) {
	if (dp[x]==nw) {mdep=f[x];}
	else {nwv&=a[f[x]];}
	if (dp[x]==0) {gt(nwv&a[x],mdep);}
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		if (v[x][i]==f[x]) {continue;}
		dfs2(v[x][i],dep+1,mdep,nwv);
	}
	return;
}
int main () {
	ex[0]=1;
	for (int i=1;i<P;i++) {
		ex[i]=(1ll*ex[i-1]*10)%P;
		lg[ex[i]]=i;
	}
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		ans=(ans+calc(a[i]))%P;
	}
	for (int i=1;i<=n-1;i++) {
		scanf("%d%d",&x,&y);
		v[x].push_back(y),v[y].push_back(x);
	}
	for (int i=1;i<=n;i++) {
		if (v[i].size()==1) {lf[++cnt]=i;}
	}
	for (int i=1;i<=cnt;i++) {
		for (int j=0;j<30;j++) {las[0][j]=make_pair(0,j);}
		dfs1(lf[i],0);
		dfs2(lf[i],1,0,(1<<30)-1);
		b[lf[i]]=1,nw++;
		//cout << i << "  " << lf[i] << "  " << ans << endl;
	}
	printf("%d\n",ans);
	return 0;
}

---

F. Unknown Mother-Goose

难度：$\bigstar\bigstar\bigstar\bigstar$

题目大意：

给定 $n$ 和一个正整数集合 $S$，求 $x$ 的数量，使得：

• $3\leq x\leq n$；
• 存在 $a\in S$ 使得 $a\mid x$；
• 存在 $b\in S$ 使得 $b\mid (x-1)$；
• 存在 $c\in S$ 使得 $c\mid (x-2)$。

$3\leq n\leq 10^9, |S|\leq 20$

题目解法：

考虑暴力，复杂度是 $O(n+\sum\limits_{x\in S}\dfrac{n}{x})$，难以通过。

使用位运算来加速这一过程，设一个长度为 $n+1$ 的 $\texttt{01}$ 串 $T$ 满足：$T_i$ 为 $\texttt{1}$ 当且仅当 $i-1$ 是某个 $x\in S$ 的倍数。

我们要查询的是 $T$ 中有多少个连续三个 $\texttt{1}$，如果压位存储，只需要类似 popcount(T|(T>>1)|(T>>2)) 的运算就可以求出答案了。

用 unsigned long long 存储 $T$，但我们还是没有减小这个 $\dfrac{n}{x}$ 的复杂度，因此还要对 $x$ 分类讨论：

• 如果 $x\ge 64$，那么直接采用 $\dfrac{n}{x}$ 的暴力算法；
• 如果 $x<64$，那么 $x$ 的倍数对应的对 $T$ 的影响是周期的，有一个周期是 $64x$，而 $64$ 恰好又是 unsigned long long 的位数，我们只要用一个辅助数组存储 $x$ 对 $T$ 的前 $x$ 个 unsigned long long 单元的影响，然后周期性地将它的第 $i$ 个单元或到 $T$ 的第 $jx+i$ 个单元即可，利用位运算，可以做到复杂度 $O(\dfrac{n}{64}+64)$。

时间复杂度为 $O(\dfrac{n|S|}{w})$，其中 $w=64$。

代码

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=1000000000;
ull bs[(MAXN>>6)+70],tmp[70];
int n,m,s,x,sss,ans,cnt[100010];
int gt (ull x) {return (x==0?0:gt(x>>16)+cnt[x&sss]);}
int main () {
	scanf("%d%d",&n,&m);
	for (int i=1;i<(1<<16);i++) {cnt[i]=cnt[i-(i&(-i))]+1;}
	s=(n>>6)+1,sss=(1<<16)-1;
	for (int i=1;i<=m;i++) {
		scanf("%d",&x);
		if (x<64) {
			memset(tmp,0,sizeof(tmp));
			for (int j=0;j<(x<<6);j+=x) {tmp[j>>6]|=(1ull<<(j&63));}
			for (int j=0;j<=(n>>6);j+=x) {
				for (int k=0;k<x;k++) {bs[j+k]|=tmp[k];}
			}
		} else {
			for (int j=0;j<=n;j+=x) {bs[j>>6]|=(1ull<<(j&63));}
		}
	}
	bs[0]--;
	if ((n&63)!=63) {bs[n>>6]&=((2ull<<(n&63))-1);}
	for (int j=0;j<=(n>>6);j++) {ans+=gt(bs[j]&(bs[j]>>1)&(bs[j]>>2));}
	for (int j=0;j<(n>>6);j++) {
		ans+=gt(bs[j+1]&(bs[j+1]>>1)&(bs[j]>>63));
		ans+=gt(bs[j+1]&(bs[j]>>63)&(bs[j]>>62));
	}
	printf("%d\n",ans);
	return 0;
}