AtCoder Beginner Contest 262 A-E题解()

特别鸣谢

介于本人比较菜鸡,参考了以下题解,在此作出感谢:
https://www.cnblogs.com/YunQianQwQ/p/16538317.html 作者@云浅の小窝

A-World Cup

用 while 循环一直加到合法。

B-Triangle (Easier)

暴力枚举并判断。

C-Min Max Pair

首先如果 \(a_i=i,a_j=j\) 的话,直接找有多少个值等于编号的,然后答案加上其选 \(2\) 个的组合数。

如果 \(a_i=j,a_j=i\),那就枚举每个数,看是否有 \(a_{a_i}=i\) 即可,注意要满足条件 \(a_i>i\)。

D-I Hate Non-integer Number

首先一上来看到暴力不行就想到 dp,我最先想到设 \(f(i,j,k)\) 代表前 \(i\) 个里选 \(j\) 个,和模 \(j\) 的值为 \(k\)。

考虑转移,如果第 \(i\) 个不选,\(f(i,j,k)=f(i-1,j,k)\)。
如果第 \(i\) 个选,这时候出现了问题,我们的 \(k\) 无法转移,因为我们上一次 \(k\) 的值为 \((sum-a_i)\bmod (j-1)\),而我们没有记录 \(sum\),是无法表示的。

所以说我们必须要有一个确定的模数,改变状态为:前 \(i\) 个里选 \(j\) 个,和模 \(t\) 的值为 \(k\),其中的 \(t\) 我们当作模数,放到最开始枚举,转移为:
第 \(i\) 个不选:\(f(i,j,k)=f(i-1,j,k)\)。
第 \(i\) 个选:\(f(i,j,k)=f(i-1,j-1,(k-a_i)\bmod t)\)。

最后的答案为所有 \(f(n,t,0)\) 的和。

Code

for(int t=1;t<=n;t++)
{
	memset(f,0,sizeof f);
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
	for(int j=0;j<=t;j++)
	for(int k=0;k<t;k++)
	{
		f[i][j][k]+=f[i-1][j][k],f[i][j][k]%=mod;
		if(j>0)f[i][j][k]+=f[i-1][j-1][((k-a[i])%t+t)%t],f[i][j][k]%=mod;
	}
	ans+=f[n][t][0];
	ans%=mod;
}

E-Red and Blue Graph

这题有点神。。。
设一个点如果被涂成蓝色,则它的点权为 \(1\),如果被涂成红色,则它的点权为 \(0\)。如果一条边连接 \(u,v\),它的边权就是 \(u\) 的点权异或上 \(v\) 的点权。

那么要满足偶数条边连接不同的点,就必须所有边权异或起来等于 \(0\)。

首先蓝点的点权不会影响答案。考虑一个红点,它的点权被异或上的次数就是它的度,如果它的度为偶数,就不会影响答案;如果它的度为奇数,则必须与另一个度为奇数的红点一起。

设 \(a\) 为度是偶数的点的个数,\(b\) 为度是奇数的点的个数,那么答案为:

即度是奇数的红点必须成对出现。

然后就是简单组合数问题,预处理阶乘,除法就跑乘法逆元。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x)
{
	char ch=getchar();
	int r=0,w=1;
	while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
	x=r*w;
}
const int mod=998244353,N=2e5+7;
int t[N],p[N];
void init()
{
	p[0]=1;
	for(int i=1;i<=2e5;i++)p[i]=p[i-1]*i,p[i]%=mod;
}
int Pow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans%mod;
}
int C(int n,int m)
{
	if(n<m)return 0;
	if(m==0)return 1;
	return p[n]*Pow(p[m],mod-2)%mod*Pow(p[n-m],mod-2)%mod;
}
main()
{
	init();
	int n,m,k;
	read(n);read(m);read(k);
	for(int i=1,x,y;i<=m;i++)
	{
		read(x);read(y);
		t[x]++;t[y]++;
	}
	int a=0,b=0;
	for(int i=1;i<=n;i++)
	{
		if(t[i]%2==0)a++;
		else b++;
	}
	int ans=0;
	for(int i=0;i<=min(b/2,k/2);i++)
		ans+=C(b,i*2)*C(a,k-i*2),ans%=mod;
	cout<<ans%mod;
	return 0;
}
————————

特别鸣谢

介于本人比较菜鸡,参考了以下题解,在此作出感谢:
https://www.cnblogs.com/YunQianQwQ/p/16538317.html 作者@云浅の小窝

A-World Cup

用 while 循环一直加到合法。

B-Triangle (Easier)

暴力枚举并判断。

C-Min Max Pair

首先如果 \(a_i=i,a_j=j\) 的话,直接找有多少个值等于编号的,然后答案加上其选 \(2\) 个的组合数。

如果 \(a_i=j,a_j=i\),那就枚举每个数,看是否有 \(a_{a_i}=i\) 即可,注意要满足条件 \(a_i>i\)。

D-I Hate Non-integer Number

首先一上来看到暴力不行就想到 dp,我最先想到设 \(f(i,j,k)\) 代表前 \(i\) 个里选 \(j\) 个,和模 \(j\) 的值为 \(k\)。

考虑转移,如果第 \(i\) 个不选,\(f(i,j,k)=f(i-1,j,k)\)。
如果第 \(i\) 个选,这时候出现了问题,我们的 \(k\) 无法转移,因为我们上一次 \(k\) 的值为 \((sum-a_i)\bmod (j-1)\),而我们没有记录 \(sum\),是无法表示的。

所以说我们必须要有一个确定的模数,改变状态为:前 \(i\) 个里选 \(j\) 个,和模 \(t\) 的值为 \(k\),其中的 \(t\) 我们当作模数,放到最开始枚举,转移为:
第 \(i\) 个不选:\(f(i,j,k)=f(i-1,j,k)\)。
第 \(i\) 个选:\(f(i,j,k)=f(i-1,j-1,(k-a_i)\bmod t)\)。

最后的答案为所有 \(f(n,t,0)\) 的和。

Code

for(int t=1;t<=n;t++)
{
	memset(f,0,sizeof f);
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
	for(int j=0;j<=t;j++)
	for(int k=0;k<t;k++)
	{
		f[i][j][k]+=f[i-1][j][k],f[i][j][k]%=mod;
		if(j>0)f[i][j][k]+=f[i-1][j-1][((k-a[i])%t+t)%t],f[i][j][k]%=mod;
	}
	ans+=f[n][t][0];
	ans%=mod;
}

E-Red and Blue Graph

这题有点神。。。
设一个点如果被涂成蓝色,则它的点权为 \(1\),如果被涂成红色,则它的点权为 \(0\)。如果一条边连接 \(u,v\),它的边权就是 \(u\) 的点权异或上 \(v\) 的点权。

那么要满足偶数条边连接不同的点,就必须所有边权异或起来等于 \(0\)。

首先蓝点的点权不会影响答案。考虑一个红点,它的点权被异或上的次数就是它的度,如果它的度为偶数,就不会影响答案;如果它的度为奇数,则必须与另一个度为奇数的红点一起。

设 \(a\) 为度是偶数的点的个数,\(b\) 为度是奇数的点的个数,那么答案为:

即度是奇数的红点必须成对出现。

然后就是简单组合数问题,预处理阶乘,除法就跑乘法逆元。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x)
{
	char ch=getchar();
	int r=0,w=1;
	while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
	x=r*w;
}
const int mod=998244353,N=2e5+7;
int t[N],p[N];
void init()
{
	p[0]=1;
	for(int i=1;i<=2e5;i++)p[i]=p[i-1]*i,p[i]%=mod;
}
int Pow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans%mod;
}
int C(int n,int m)
{
	if(n<m)return 0;
	if(m==0)return 1;
	return p[n]*Pow(p[m],mod-2)%mod*Pow(p[n-m],mod-2)%mod;
}
main()
{
	init();
	int n,m,k;
	read(n);read(m);read(k);
	for(int i=1,x,y;i<=m;i++)
	{
		read(x);read(y);
		t[x]++;t[y]++;
	}
	int a=0,b=0;
	for(int i=1;i<=n;i++)
	{
		if(t[i]%2==0)a++;
		else b++;
	}
	int ans=0;
	for(int i=0;i<=min(b/2,k/2);i++)
		ans+=C(b,i*2)*C(a,k-i*2),ans%=mod;
	cout<<ans%mod;
	return 0;
}