526互联

AtCoder Grand Contest 035

发布时间 2023-09-27 19:00:14作者: Zhou_JK

A - XOR Circle

可以发现，相邻三个数的异或和一定为 \(0\)。如果三个字符已经确定了，那么整个字符串就已经确定为这三个字符构成，且序列唯一。

如果 \(n\bmod 3\ne 0\)，显然无解。

如果字符集的大小大于 \(3\)，显然无解。

如果字符集的大小等于 \(3\)，只有在这三种字符连成环的情况合法，即这三种字符的个数相等。

如果字符集的大小等于 \(2\)，相邻的三个字符中两个相等，剩下一个必须为 \(0\)，合法的情况即为 \(0\) 的个数为 \(\frac{n}{3}\)，剩下的字符个数为 \(2\cdot \frac{n}{3}\)。

如果字符集的大小等于 \(1\)，只有当序列全为 \(0\) 时合法。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int a[N];
int cnt[N],num[N],tot;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	if(a[1]==a[n]&&a[1]==0)
	{
		printf("Yes");
		return 0;
	}
	a[0]=-1;
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=a[i-1]) tot++,num[tot]=a[i],cnt[tot]=1;
		else cnt[tot]++;
		if(tot>3)
		{
			printf("No");
			return 0;
		}
	}
	if(n%3!=0)
	{
		printf("No");
		return 0;
	}
	if(tot==3)
	{
		if((num[1]^num[2]^num[3])==0&&cnt[1]==cnt[2]&&cnt[2]==cnt[3]) printf("Yes");
		else printf("No");
	}
	else if(tot==2)
	{
		if(a[1]==0&&cnt[1]==n/3) printf("Yes");
		else printf("No");
	}
	else printf("No");
	return 0;
}

B - Even Degrees

如果 \(m\) 为奇数时肯定无解，对于 \(m\) 为偶数的情况我们考虑构造出一种方案。

考虑原图的一棵生成树，对于生成树外的边我们可以随意确定。考虑从下到上确定每一条边的方向，对于父亲 \(u\) 向儿子连的边 \((u,v)\)，如果 \(v\) 的出度为奇数，连 \(v\to u\)，否则连 \(u\to v\)，可以证明这样构造一定是正确的。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=100005;
int n,m;
vector<int>G[N];
int d[N];
int x[N],y[N];
int fa[N];
int getf(int v)
{
	if(v==fa[v]) return v;
	fa[v]=getf(fa[v]);
	return fa[v];
}
bool merge(int u,int v)
{
	int f1=getf(u),f2=getf(v);
	if(f1!=f2)
	{
		fa[f2]=f1;
		return true;
	}
	else return false;
}
vector<pair<int,int> >res;
void kruskal()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
		if(merge(x[i],y[i])) G[x[i]].push_back(y[i]),G[y[i]].push_back(x[i]);
		else res.push_back(make_pair(x[i],y[i])),d[x[i]]++;
	return;
}
void dfs(int u,int father)
{
	for(int v:G[u])
	{
		if(v==father) continue;
		dfs(v,u);
		if(d[v]&1) res.push_back(make_pair(v,u)),d[v]++;
		else res.push_back(make_pair(u,v)),d[u]++;
	}
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&x[i],&y[i]);
	if(m&1)
	{
		printf("-1");
		return 0;
	}
	kruskal();
	dfs(1,0);
	for(auto [u,v]:res)
		printf("%d %d\n",u,v);
	return 0;
}

C - Skolem XOR Tree

可以发现，对于偶数 \(i\)，满足 \(i\oplus (i+1)=1\)。

对于 \(n\) 为奇数的情况，我们可以将所有的点都连在 \(1\) 上（注意 \(2,3\) 比较特殊），具体如下图：

agc035c.png

\(n\) 为偶数的情况，如果 \(n\) 为 \(2\) 的幂次时显然无解，因为 \(n\) 显然无法用比它小的数的异或和表示出来。否则可以暴力找出一个 \(x,y\) 使得 \(x\oplus 1\oplus y=n\)，将 \(n\) 和 \(n+n\) 接到 \(x,y\) 上即可。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=100005;
int n;
vector<pair<int,int> >res;
int main()
{
	scanf("%d",&n);
	int k=1;
	while(k<n) k<<=1;
	if(k==n)
	{
		printf("No");
		return 0;
	}
	res.push_back(make_pair(1,2));
	res.push_back(make_pair(2,3));
	res.push_back(make_pair(3,n+1));
	res.push_back(make_pair(n+1,n+2));
	res.push_back(make_pair(n+2,n+3));
	for(int i=2;2*i+1<=n;i++)
	{
		res.push_back(make_pair(2*i,2*i+1));
		res.push_back(make_pair(2*i+1,n+1));
		res.push_back(make_pair(n+1,n+2*i));
		res.push_back(make_pair(n+2*i,n+2*i+1));
	}
	if(n%2==0)
	{
		for(int x=2;x<=n-1;x++)
		{
			int y=n^1^x;
			if(y!=x&&y>=2&&y<=n-1)
			{
				int i,j;
				if(x&1) i=x;
				else i=x+n;
				if(y&1) j=y;
				else j=y+n;
				res.push_back(make_pair(n,i));
				res.push_back(make_pair(n+n,j));
				break;
			}
		}
	}
	printf("Yes\n");
	for(auto [x,y]:res)
		printf("%d %d\n",x,y);
	return 0;
}

D - Add and Remove

考虑倒着往前做，对于一段区间 \([l,r]\)，不妨令合并到左端点有 \(p\) 的贡献，右端点有 \(q\) 的贡献，枚举上一个合并的位置 \(i\)，对答案的贡献即为 \((p+q) \cdot a_i\)。

对于 \([l,i-1]\) 肯定要不就是合并到左端点要不就是合并到 \(i\)，合并到 \(i\) 的贡献为 \(p+q\)，合并到左端点的贡献为 \(p\)，\([i+1,r]\) 同理。

那么就可以分治了，令 \(f_{l,r,p,q}\) 表示 \([l,r]\) 这段区间，合并到 \(l\) 的贡献为 \(p\)，合并到 \(r\) 的贡献为 \(q\) 时的最小贡献和，答案即为 \(f_{2,n-1,1,1}+a_1+a_n\)。枚举上一个合并的位置 \(i\)，转移即为：

\[f_{l,r,p,q}=\min\limits_{i=l}^r\{f_{l,i-1,p,p+q}+f_{i+1,p+q,q}+(p+q)a_i\} \]

可以证明这样复杂度是对的。

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int N=25;
const long long INF=4557430888798830399;
int n;
int a[N];
map<pair<int,int>,long long>f[N][N];
long long dfs(int l,int r,int p,int q)
{
	if(l>r) return 0;
	if(f[l][r].count({p,q})) return f[l][r][{p,q}];
	long long res=INF;
	for(int i=l;i<=r;i++)
		res=min(res,dfs(l,i-1,p,p+q)+dfs(i+1,r,p+q,q)+1LL*(p+q)*a[i]);
	return f[l][r][{p,q}]=res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	printf("%lld",dfs(2,n-1,1,1)+a[1]+a[n]);
	return 0;
}

E - Develop

考虑一种删除方案是否合法，将 \(x\to x-2,x\to x+K\) 连边，表示如果要删去 \(x,x+K\)，一定先删 \(x\) 再删 \(x-2,x+K\)，如果图中无环我们就可以按照拓扑序依次删去即为合法的。我们需要算的即为有多少点集满足点集内不存在环。

称某个点被选表示这个点被选进了删除的集合内。

对于 \(x\to x-2\) 的边，可以发现，这个就是两条链。

考虑加入 \(x\to x+K\) 的边。

对于 \(K\) 为偶数的情况，满足条件的最小环即为 \(a \to a-2 \to \cdots \to a-K \to a\)，即我们不能选连续的 \(\frac{K}{2}-1\) 的点。

令 \(f_{i,j}\) 表示当前到了第 \(i\) 层，已经选了一个长度为 \(j\) 的连续段的方案数。转移时枚举当前点选还是不选转移即可。

对于 \(K\) 为奇数的情况，满足条件的最小环为经过了 \(2\) 条 \(K\) 的边的环。将图分成奇数和偶数两部分，将左部的 \(x\) 和右部的 \(x+K\) 的点放在同一层，图即为以下的样子：

agc035e.png

可以发现，最小环即为 \(a \to a-2 \to \cdots \to b-K \to b \to b-2 \to \cdots \to a-K \to a\)，如果若干条向上边，\(1\) 条向右边，若干条向上边的长度 \(> K+1\) 就会有环。

令 \(f_{i,j,k}\) 表示考虑前 \(i\) 层，从第 \(i\) 层左边经过若干条向上边，\(1\) 条向右边，若干条向上边的最长链为 \(j\)，从第 \(i\) 层向上的连续边的最长链为 \(k\) 的方案数。转移时分两个点都不选和两个点都选，或者选左边或者右边的点，注意一定要有向右的边。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=305;
int n,K,P;
namespace subtask1
{
	long long f[N][N];
	int main()
	{
		f[0][0]=1;
		for(int i=1;i<=(n+1)/2;i++)
		{
			for(int j=0;j<=K/2;j++)
				f[i][0]=(f[i][0]+f[i-1][j])%P;
			for(int j=0;j<=K/2-1;j++)
				f[i][j+1]=(f[i][j+1]+f[i-1][j])%P;
		}
		long long ans1=0,ans0=0;
		for(int j=0;j<=K/2;j++)
			ans1=(ans1+f[(n+1)/2][j])%P;
		for(int j=0;j<=K/2;j++)
			ans0=(ans0+f[n/2][j])%P;
		printf("%lld",ans1*ans0%P);
		return 0;
	}
}
namespace subtask2
{
	long long f[N][N][N];
	int main()
	{
		f[0][0][0]=1;
		int i;
		for(i=2;i<=n+K;i+=2)
		{
			for(int j=0;j<=K+1;j++)
				for(int k=0;k<=n;k++)
					f[i][0][0]=(f[i][0][0]+f[i-2][j][k])%P;
			if(i<=n)
			{
				for(int j=0;j<=K+1;j++)
					for(int k=0;k<=n;k++)
						f[i][0][k+1]=(f[i][0][k+1]+f[i-2][j][k])%P;
			}
			if(i>=K+1)
			{
				for(int j=0;j<=K+1;j++)
					for(int k=0;k<=n;k++)
						f[i][j+(j!=0)][0]=(f[i][j+(j!=0)][0]+f[i-2][j][k])%P;
			}
			if(i<=n&&i>=K+1)
			{
				for(int j=0;j<=K+1;j++)
					for(int k=0;k<=n;k++)
						f[i][max(j+1,k+2)][k+1]=(f[i][max(j+1,k+2)][k+1]+f[i-2][j][k])%P;
			}
		}
		i-=2;
		long long ans=0;
		for(int j=0;j<=K+1;j++)
			for(int k=0;k<=n;k++)
				ans=(ans+f[i][j][k])%P;
		printf("%lld",ans);
		return 0;
	}
}
int main()
{
	scanf("%d%d%d",&n,&K,&P);
	if(K%2==0) return subtask1::main();
	else return subtask2::main();
	return 0;
}

F - Two Histograms

考虑重复的情况，对于第 \(i\) 行和第 \(j\) 列，只有当 \(r_i=j,c_j=i-1\) 和 \(r_i=j-1,c_j=i\) 时会相同。具体证明可以看官方题解。

那么就可以容斥了，枚举至少有 \(k\) 个位置重复，那么这种情况的方案即为：

\[C_n^k C_m^k \cdot k! \cdot (M+1)^{n-k}(N+1)^{m-k} \]

直接容斥即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=500005;
const int MOD=998244353;
int n,m;
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
long long fac[N],inv[N];
void init(int n=500000)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%MOD;
	return;
}
long long C(int n,int m)
{
	if(m>n) return 0;
	else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
long long f(int k)
{
	return C(n,k)*C(m,k)%MOD*fac[k]%MOD*ksm(m+1,n-k)%MOD*ksm(n+1,m-k)%MOD;
}
int main()
{
	init();
	scanf("%d%d",&n,&m);
	long long ans=0;
	for(int i=0;i<=min(n,m);i++)
		if(i&1) ans=(ans-f(i)+MOD)%MOD;
		else ans=(ans+f(i))%MOD;
	printf("%lld",ans);
	return 0;
}