补题情况

题目	蒋贤蒙	王赵安	王智彪
B	0	0	0
C	2	0	1
F	2	0	1
G	0	0	0
H	1	0	2
I	0	0	0
J	2	1	0

题解

C. Fuzzy Graph

题意

给定一个连通图，要求将图上每个点染成 $\text{RGB}$ 三种颜色。对应边 $(u,v)$，如果 $u,v$ 同色，则该边染成 $u,v$ 的颜色，否则该边染成黑色。

要求构造一种染色方案，使得删除图中所有非黑边仍然可以使图连通，同时满足如下两个条件之一：

$\text{RGB}$ 三种颜色的点一样多，数据保证 $3\mid n$
$\text{X}$ 是点集中出现次数最多的颜色(允许有其他颜色出现次数和他相同)，且不存在边的颜色为 $\text{X}$

题解

首先跑一遍 $\text{dfs}$ 树，然后用 $\text{RG}$ 两种颜色进行二染色，这样所有树边都是黑色边，图保证连通。

接下来，设 $c_0$ 表示 $\text{R}$ 颜色在点集中出现的次数，设 $c_1$ 表示 $\text{G}$ 颜色在点集中出现的次数。

若 $c_0\le \frac n3$ 或者 $c_1\le \frac n3$，则考虑构造第二个条件：将所有叶子结点染成颜色 $\text{B}$。

事实上，由于叶子结点在 $\text{dfs}$ 树上只有返祖边，所以所有叶子节点之间一定没有连边，即不存在颜色为 $\text{B}$ 的边。

另一方面，不妨设 $c_0\le \frac n3$，则所有颜色为 $G$ 的非叶子结点至少是一个颜色为 $R$ 的结点的父亲，所以所有颜色为 $G$ 的非叶子结点个数不超过 $\frac n3$。

由于颜色为 $R$ 的非叶子结点个数不超过颜色为 $R$ 的结点总个数 $c_0$，所有颜色为 $R$ 的非叶子结点个数也不超过 $\frac n3$。

所以叶子结点总个数一定不小于 $\frac n3$，且将叶子结点染成 $B$ 后 $B$ 出现次数一定最多。

若 $c_0\ge \frac n3$ 且 $c_1\ge \frac n3$，则考虑构造第一个条件：从深到浅贪心染色，如果当前结点颜色出现个数大于 $\frac n3$ 且相邻结点颜色不为 $B$，则染成 $B$。

事实上，设 $c_0=\frac n3+d_0,c_1=\frac n3+d_1$，根据上述构造，易知 $G$ 被染色成 $B$ 的个数不超过 $d_1$。

而由于是从深到浅染色，所以每个从 $G$ 被染色成 $B$ 的结点只会 $\text{ban}$ 他的父结点，不考虑 $\text{ban}$ 儿子结点。

所有 $R$ 结点的可选染色位置最多被 $\text{ban}$ $d_1$ 个位置，于是要从余下 $\frac n3+d_0-d_1$ 个位置中选出 $d_0$ 个位置，这一定是可行的。

同理，所有 $G$ 结点一定也可以选出 $d_1$ 个位置染成 $B$。

总时间复杂度 $O(n+m)$。

查看代码

const int MAXN=3e5+5,MAXM=5e5+5;
const char s[]="RGB";
struct Edge{
	int to,next;
}edge[MAXM<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt]=Edge{v,head[u]};
	head[u]=edge_cnt;
}
int ans[MAXN],fa[MAXN],d[MAXN],cnt[2];
bool fib[MAXN];
vector<int> node[MAXN],leaf;
void dfs(int u,int f){
	ans[u]=ans[f]^1;
	cnt[ans[u]]++;
	d[u]=d[f]+1;
	fa[u]=f;
	node[d[u]].push_back(u);
	bool flag=false;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==f||d[v])continue;
		flag=true;
		dfs(v,u);
	}
	if(!flag)
	leaf.push_back(u);
}
void solve(){
	int n=read_int(),m=read_int();
	_rep(i,1,n){
		head[i]=0;
		d[i]=0;
		fib[i]=false;
		node[i].clear();
	}
	cnt[0]=cnt[1]=0;
	leaf.clear();
	edge_cnt=0;
	while(m--){
		int u=read_int(),v=read_int();
		Insert(u,v);
		Insert(v,u);
	}
	dfs(1,0);
	if(cnt[0]<=n/3||cnt[1]<=n/3){
		for(int v:leaf)
		ans[v]=2;
	}
	else{
		for(int i=n-1;i;i--){
			for(int v:node[i]){
				if(fib[v]||cnt[ans[v]]==n/3)continue;
				cnt[ans[v]]--;
				ans[v]=2;
				fib[fa[v]]=true;
			}
		}
	}
	_rep(i,1,n)
	putchar(s[ans[i]]);
	putchar('\n');
}
int main(){
	int T=read_int();
	while(T--)
	solve();
	return 0;
}

H.Scholomance Academy

注意到 $F(n)$ 是一个积性函数，因为对于两堆不同的质因子放进去，因为欧拉函数是积性函数，我都可以分成两堆，一堆装第一类，一堆装第二类，然后发现和单独相乘是一一对应的关系，必然相等。

于是我们单独对每个质因子拆开计算。

我们考虑生成函数 $G_{p}(x)=F(p^{0})+F(p^{1})x^{1}+\ldots$ ，然后所有质因子的生成函数乘起来的 $N$ 次项就是 $G(N)$ 的结果了。

这东西等于 $(\phi (p^{0})+\phi (p^{1})x^{1}+\ldots)^{m}$

化简得到 $(\frac {1-x} {1-px})^{m}$ ，然后所有的质因子乘起来，最后分子分母都是最高次项为 $mt$ 次方的多项式，设除的结果为 $h(x)$ ，我们要求 $h(x)$ 的第 $n$ 次项，设分子为 $f(x)$ ，分母为 $g(x)$ 。

然后这东西是可以常系数齐次线性递推搞的：对于高于 $mt$ 次的系数，$[x^{n}]f(x)$ 必然是 $0$ ，然后有： $[x^{n}]f(x)=0=\sum_{i=0}^{mt}[x^{n-i}]h(x)×[x^{i}]g(x)$ ，然后我们就有 $[x^{n}]h(x)×[x^{0}]g(x)=-\sum_{i=1}^{mt}[x^{n-i}]h(x)×[x^{i}]g(x)$ ，这玩意求逆元化简之后，就变成了一个常系数齐次线性递推的板子。

这里有两个需要注意的地方， $n$ 比较小的时候，是要直接输出多项式逆元乘法的第 $N$ 项，然后递推的时候递推的系数是 $[x^{1}]g(x)$ 到 $[x^{mt}]g(x)$ 然后因为 $[x^{mt}]f(x)≠0$ ，所以这个 $N$ 要从 $mt+1$ 开始取，也就是说要我们初始项是 $[x^{1}]h(x)$ 到 $[x^{mt}]h(x)$ 然后就需要向前挪一项，然后求 $N-1$ 次的系数。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2000006,GG=3,GI=332748118,mod=998244353;
 
inline void read(int &X) {
	X = 0;
	int w=0;
	char ch=0;
	while(!isdigit(ch)) {
		w|=ch=='-';
		ch=getchar();
	}
	while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
	if (w) X = -X;
}
namespace my_f {
	int qpow(int a,int b,int m=mod) {
		int r=1;
		while(b) {
			if (b&1) r=r*a%m;
			a=a*a%m,b>>=1;
		}
		return r;
	}
	int pgg[50],pgi[50];
	void init() {
		for(int i=0; i<=48; i++) {
			pgg[i]=qpow(GG,(mod-1)>>i);
			pgi[i]=qpow(GI,(mod-1)>>i);
		}
	}
#define ad(x,y) ((x)+(y)>mod?(x)+(y)-mod:(x)+(y))
#define dc(x,y) ((x)-(y)<0?(x)-(y)+mod:(x)-(y))
	namespace poly {
		int w[N],r[N];
		void NTT(int f[N],int lim,int type) {
			for(int i=0; i<lim; i++) if (i<r[i]) swap(f[i],f[r[i]]);
			for(int mid=1,pp=1; mid<lim; mid<<=1,++pp) {
				int Wn=(type==1?pgg[pp]:pgi[pp]);
				w[0]=1;
				for(int i=1; i<mid; i++) w[i]=w[i-1]*Wn%mod;
				for(int i=0; i<lim; i+=(mid<<1)) {
					for(int j=0; j<mid; ++j) {
						int y=f[i|mid|j]*w[j]%mod;
						f[i|mid|j]=dc(f[i|j],y);
						f[i|j]=ad(f[i|j],y);
					}
				}
			}
			if (type==-1) {
				int ivv=qpow(lim,mod-2);
				for(int i=0; i<lim; i++) f[i]=f[i]*ivv%mod;
			}
		}
		void init(int n) {
			r[0]=0;
			for(int i=1; i<n; i++)r[i]=((r[i>>1]>>1)|((i&1)*(n>>1)));
		}
		int pw[2][N],rev[N];
		void pre() {
			for(int i=1; i<N; i++)pw[0][i]=qpow(GG,(mod-1)/(i<<1)),pw[1][i]=qpow(GG,mod-1-(mod-1)/(i<<1));
		}
		void vec_NTT(vector<int> &a,int n,int o) {
			for(int i=0; i<n; i++)if(i<r[i])swap(a[i],a[r[i]]);
			for(int i=1; i<n; i<<=1) {
				int wn;
				if(o==1)wn=pw[0][i];
				else wn=pw[1][i];
				for(int j=0; j<n; j+=(i<<1)) {
					int w=1;
					for(int k=0; k<i; k++) {
						int t=w*a[i+j+k]%mod;
						w=w*wn%mod;
						a[i+j+k]=(a[j+k]-t+mod)%mod;
						a[j+k]=(a[j+k]+t)%mod;
					}
				}
			}
			if(o==-1) {
				int INV=qpow(n,mod-2);
				for(int i=0; i<=n; i++)a[i]=a[i]*INV%mod;
			}
		}
		int pool[10][N];
		inline void Inv(int f[N],int g[N],int n) { // 求逆, pool 0~2
			int *iv=pool[0],*a=pool[1],*b=pool[2];
			for(int i=0; i<=4*n; i++) iv[i]=a[i]=b[i]=0;
			iv[0]=qpow(f[0],mod-2);
 
			int len=1,lim=1;
			for(len=1; len<=(n<<1); len<<=1) {
				lim=len<<1;
 
				for(int i=0; i<=4*len; i++) a[i]=b[i]=0;
				for(int i=0; i<len; i++) a[i]=f[i],b[i]=iv[i];
				for(int i=0; i<lim; i++) r[i]=((r[i>>1]>>1)|((i&1)?len:0));
				NTT(a,lim,1);
				NTT(b,lim,1);
				for(int i=0; i<lim; i++) a[i]=(2*b[i]-a[i]*b[i]%mod*b[i]%mod+mod)%mod;
				NTT(a,lim,-1);
				for(int i=0; i<len; i++) iv[i]=a[i];
			}
			for(int i=0; i<n; i++) g[i]=iv[i];
			for(int i=n; i<lim; i++) g[i]=0;
		}
		vector<int> vec_mul(vector<int> a,vector<int> b) {
			int len=a.size()+b.size()-1,lim=1;
			while(lim<=len) lim<<=1;
			init(lim);
			a.resize(lim);
			vec_NTT(a,lim,1);
			b.resize(lim);
			vec_NTT(b,lim,1);
			for(int i=0; i<lim; i++)a[i]=a[i]*b[i]%mod;
			vec_NTT(a,lim,-1);
			a.resize(len);
			return a;
		}
		inline void mul(int f[N],int g[N],int n,bool flag=1) // *=, pool 3~4
		// flag: 是否对n取膜
		{
			int len=1,lim=1;
			while(len<=(n<<1)) len=lim,lim<<=1;
			int *a=pool[3],*b=pool[4];
			for(int i=0; i<lim; i++) a[i]=b[i]=0;
			for(int i=0; i<n; i++) a[i]=f[i],b[i]=g[i];
			for(int i=0; i<lim; i++) r[i]=((r[i>>1]>>1)|((i&1)?len:0));
			NTT(a,lim,1);
			NTT(b,lim,1);
			for(int i=0; i<lim; i++) a[i]=a[i]*b[i]%mod;
			NTT(a,lim,-1);
			for(int i=0; i<2*n; i++) f[i]=a[i];
			for(int i=2*n; i<=lim; i++) f[i]=0;
			if (flag) for(int i=n; i<2*n; i++) f[i]=0;
		}
		void Mod(int f1[N],int f2[N],int n,int m,int R[N]) // 多项式取模, pool 5~6
		// 这里只保留了余数, 商开到 pool 里而不是传参数修改了
		{
			int *a=pool[5],*b=pool[6],*Q=pool[7];
			for(int i=0; i<=4*n; i++) a[i]=b[i]=0;
			for(int i=0; i<n; i++) a[i]=f1[n-1-i];
			for(int i=n-m+1; i<n; i++) a[i]=0; // a=f1_r%(x^(n-m+1))
			for(int i=0; i<m; i++) b[i]=f2[m-1-i];
			for(int i=n-m+1; i<m; i++) b[i]=0;
			Inv(b,b,n-m+1);
			mul(a,b,n-m+1);
			for(int i=0; i<=n-m; i++) Q[i]=a[n-m-i];
 
			for(int i=0; i<=4*n; i++) a[i]=b[i]=0;
			for(int i=0; i<n; i++) a[i]=f1[i];
			for(int i=0; i<m; i++) b[i]=f2[i];
			int len=1,lim=1;
			while(len<=n) len=lim,lim<<=1;
			for(int i=0; i<lim; i++) r[i]=((r[i>>1]>>1)|((i&1)?len:0));
			NTT(b,lim,1);
			NTT(Q,lim,1);
			for(int i=0; i<lim; i++) b[i]=b[i]*Q[i]%mod;
			NTT(b,lim,-1);
			NTT(Q,lim,-1);
			for(int i=0; i<m-1; i++) R[i]=(a[i]-b[i]%mod+mod)%mod;
			for(int i=m-1; i<lim; i++) R[i]=0;
		}
		void PowMod(int f[N],int p,int g[N],int n,int h[N]) { // f^p%g, g有n项, 保存在h
			int *res=pool[8];
			for(int i=0; i<=8*n; i++) res[i]=0;
			res[0]=1; // res=1
			while(p) {
				if (p&1) {
					mul(res,f,n,0); // res*=f
					Mod(res,g,2*n,n,res); // res%=g
				}
				mul(f,f,n,0); // f=f*f
				Mod(f,g,2*n,n,f); // f%=g
				p>>=1;
			}
			for(int i=0; i<n-1; i++) h[i]=res[i];
			for(int i=n; i<=8*n; i++) h[i]=0;
		}
	}
	int n,T,m;
	int a[N],t[N],p[N],F[N],tmp[N],tmp1[N],tmp2[N],tmp3[N],fm[N],fm1[N],jc[N],inv[N];
	vector<int> work(int l,int r) {
		int mid=l+r>>1;
		if(l==r) {
			vector<int> ans(2);
			ans[0]=1,ans[1]=mod-p[l];
			return ans;
		}
		return poly::vec_mul(work(l,mid),work(mid+1,r));
	}
 
	void Input() {
		init();
		poly::pre();
		read(n);
		read(T);
		read(m);
		for(int i=1; i<=T; i++) read(p[i]);
		fm[0]=1;
		jc[0]=jc[1]=1;
		for(int i=2; i<=m*T+1; i++) {
			jc[i]=jc[i-1]*i%mod;
		}
		inv[0]=inv[1] = 1;
		for(int i=2; i<=m*T+1; ++i) {
			inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		}
		for(int i=2; i<=m*T+1; ++i) {
			inv[i]=inv[i]*inv[i-1]%mod;
		}
		vector<int> mkbk=work(1,T);
		vector<int> fm2(1);
		fm2[0]=1;
		for(int i=1; i<=m; i++) {
			fm2=poly::vec_mul(fm2,mkbk);
		}
		for(int i=0,flag=1; i<=m*T; i++,flag=-flag) {
			tmp3[i]=flag*(jc[m*T]*inv[i]%mod*inv[m*T-i]%mod)%mod;
			if(tmp3[i]<0) tmp3[i]+=mod;
		}
 
		for(int i=0; i<fm2.size(); i++) {
			fm[i]=fm2[i];
		}
		long long ttmp=qpow(fm[0],mod-2);
		for(int i=1; i<=m*T; i++) {
			fm1[i]=(mod-fm[i])*ttmp%mod;
		}
		poly::Inv(fm,tmp2,m*T+1);
		poly::mul(tmp2,tmp3,m*T+1,1);
		if(n<=m*T) {
			printf("%lld\n",tmp2[n]);
			exit(0);
		}
		for(int i=m*T+1; i<=2*m*T; i++) tmp2[i]=0;
		for(int i=0;i<=m*T;i++) {
			tmp2[i]=tmp2[i+1];
		}
	}
	int f[N],g[N],c[N];
	void Sakuya() {
		f[1]=1;
		for(int i=1; i<=m*T; i++) g[m*T-i]=(mod-fm1[i]);
		g[m*T]=1;
		poly::PowMod(f,n-1,g,m*T+1,c);
 
		int ans=0;
		for(int i=0; i<m*T; i++) ans=(ans+tmp2[i]*c[i]%mod)%mod;
		printf("%lld\n",ans);
	}
 
}
#undef int
using namespace my_f;
int main() {
	Input();
	Sakuya();
	return 0;
}

J. Tree

题意

给定一棵树和两个人的初始位置 $s,t$。两个人在树上轮流移动，两个人走过的点都不能再走且两个人不能在同一个点。

每个人的分数为自己无法移动时走过的点数，两个人都希望最大化自己和另一个人的分数差，问最终先手的分数减去后手分数的值。

题解

首先以先手为根建树，树形 $\text{dp}$ 求出每个点 $u$ 不经过 $s,t$ 链上的点能到达的最远距离 $a(u)$。设链上的点为 $v_1,v_2\cdots v_k$，其中 $v_1=s,v_k=t$。

定义 $\text{solve}(l,r,0/1)$ 表示第一个人位于 $v_l$ 第二个人位于 $v_r$，$0/1$ 表示轮到先手/后手行动的答案。

对 $\text{solve}(l,r,0)$，先手如果选择进入子树，此时答案为 $a(v_l)+l-1-\max_{l\lt x\le r}(a(v_x)+k-x)$。

如果选择不进入子树，则答案为 $\text{solve}(l+1,r,1)$。所以两种情况取 $\max$ 即可，后手情况类似。

上述转移可以使用 $\text{ST}$ 表，时间复杂度 $O(n\log n)$。

查看代码

const int MAXN=5e5+5,MAXM=20;
struct Edge{
	int to,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt]=Edge{v,head[u]};
	head[u]=edge_cnt;
}
int p[MAXN];
multiset<int> dp[MAXN];
void dfs(int u,int fa){
	dp[u].insert(1);
	p[u]=fa;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,u);
		dp[u].insert(*dp[v].rbegin()+1);
	}
}
struct ST{
	int d[MAXN][MAXM],lg2[MAXN];
	void build(int *a,int n){
		lg2[1]=0;
		_rep(i,2,n)
		lg2[i]=lg2[i>>1]+1;
		_for(i,0,n)
		d[i][0]=a[i];
		for(int j=1;(1<<j)<=n;j++){
			_for(i,0,n+1-(1<<j))
			d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
		}
	}
	int query(int lef,int rig){
		int len=rig-lef+1;
		return max(d[lef][lg2[len]],d[rig-(1<<lg2[len])+1][lg2[len]]);
	}
}st1,st2;
int mv1[MAXN],mv2[MAXN];
int solve(int l,int r,int pos){
	if(l+1==r)
	return mv1[l]-mv2[r];
	if(pos==0)
	return max(mv1[l]-st2.query(l+1,r),solve(l+1,r,!pos));
	else
	return min(st1.query(l,r-1)-mv2[r],solve(l,r-1,!pos));
}
int main(){
	int n=read_int(),s=read_int(),t=read_int();
	_for(i,1,n){
		int u=read_int(),v=read_int();
		Insert(u,v);
		Insert(v,u);
	}
	dfs(s,0);
	vector<int> vec;
	int pos=t;
	while(pos){
		vec.push_back(pos);
		pos=p[pos];
	}
	reverse(vec.begin(),vec.end());
	_for(i,0,vec.size()){
		int v=vec[i];
		if(i!=vec.size()-1){
			int v2=vec[i+1];
			dp[v].erase(dp[v].find(*dp[v2].rbegin()+1));
		}
	}
	_for(i,0,vec.size()){
		mv1[i]=*dp[vec[i]].rbegin()+i;
		mv2[i]=*dp[vec[i]].rbegin()+vec.size()-i-1;
	}
	st1.build(mv1,vec.size());
	st2.build(mv2,vec.size());
	enter(solve(0,vec.size()-1,0));
	return 0;
}

CVBB ACM Team

目录

补题情况

题解

C. Fuzzy Graph

题意

题解

H.Scholomance Academy

J. Tree

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

补题情况

题解

C. Fuzzy Graph

题意

题解

H.Scholomance Academy

J. Tree

题意

题解

页面工具