526互联

AtCoder Grand Contest 046

发布时间 2023-09-27 18:55:08作者: Zhou_JK

A - Takahashikun, The Strider

问题就是要你求 \(ax\equiv 0 \pmod{360}\) 中 \(a\) 的最小值。

答案就是 \(a=\frac{360}{\gcd(x,360)}\)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int x;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
	scanf("%d",&x);
	printf("%d",360/gcd(x,360));
	return 0;
}

B - Extension

考虑 DP，令 \(f_{i,j}\) 表示当前填了 \(i\) 行 \(j\) 列的方案数，因为先填行再填列和先填列再填行有重合部分，需要减去，转移为：

\[f_{i,j}=if_{i,j-1}+jf_{i-1,j}-(i-1)(j-1)f_{i-1,j-1} \]

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3005;
const int MOD=998244353;
int A,B,C,D;
long long dp[N][N];
long long dfs(int r,int c)
{
	if(r<A||c<B) return 0;
	if(dp[r][c]!=-1) return dp[r][c];
	int res=0;
	res=(res+dfs(r,c-1)*r%MOD)%MOD;
	res=(res+dfs(r-1,c)*c%MOD)%MOD;
	res=(res-dfs(r-1,c-1)*(r-1)%MOD*(c-1)%MOD+MOD)%MOD;
	return dp[r][c]=res;
}
int main()
{
	scanf("%d%d%d%d",&A,&B,&C,&D);
	memset(dp,-1,sizeof(dp));
	dp[A][B]=1;
	printf("%lld",dfs(C,D));
	return 0;
}

C - Shift

不妨将所有的根据 \(0\) 分成若干段，令 \(f_{i,j,k}\) 表示当前填的 \(i\) 段，用了 \(j\) 个 \(1\)，用了 \(k\) 次操作，转移时枚举当前段填的 \(1\) 的个数。

\[f_{i,j,k}=\sum f_{i-1,j-p,k-\max(p-a_i,0)} \]

\(a_i\) 为当前段 \(1\) 的个数。

直接实现为 \(O(n^4)\) 的，可以用前缀和瞎 jb 搞一下就是 \(O(n^3)\) 的了，代码是 \(O(n^4)\) 的。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=305;
const int MOD=998244353;
int n,m;
char s[N];
int a[N];
int sum[N];
long long dp[N][N][N];
int main()
{
	scanf("%s%d",s+1,&m);
	n=strlen(s+1);
	s[++n]='0';
	m=min(m,n);
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(s[i]=='0') cnt++;
		else a[cnt+1]++;
	for(int i=1;i<=cnt;i++)
		sum[i]=sum[i-1]+a[i];
	dp[0][0][0]=1;
	for(int i=1;i<=cnt;i++)
		for(int j=sum[i];j<=n-cnt;j++)
			for(int k=0;k<=m;k++)
				for(int p=0;p<=min(j,n-sum[i-1]-cnt);p++)
					if(k>=max(p-a[i],0)) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-p][k-max(p-a[i],0)])%MOD;
	long long ans=0;
	for(int k=0;k<=m;k++)
		ans=(ans+dp[cnt][n-cnt][k])%MOD;
	printf("%lld",ans);
	return 0;
}

D - Secret Passage

考虑一个分界点 \(i\)，我们需要知道 \(i\) 前面经过若干次操作后是否能得出 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 到后面，还有 \(i\) 后面加入 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 后能够得到多少种不同的方案。

考虑计算 \(i\) 前面经过若干次操作后是否能得出 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 到后面，令 \(f_{i,c_0,c_1}\) 表示当前到第 \(i\) 个位置，是否可以取出 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 扔到后面。那么对于 \(f_{i,c_0,c_1}\)，考虑它如何转移：

  • 当前点可以不动；
  • 当 \(s_{i+1}=0\) 时，我们可以将一个扔到后面的 \(1\) 换成 \(0\)；
  • 当 \(s_{i+1}=1\) 时同理；
  • 当 \(s_{i+1}=0\) 或 \(s_{i+2}=0\) 时，我们可以将一个 \(0\) 扔到后面，另一个数去掉；
  • 当 \(s_{i+1}=1\) 或 \(s_{i+2}=1\) 时同理。

对应的转移为：

\[f_{i,c_0,c_1}\to \begin{cases} f_{i+1,c_0,c_1} \\ f_{i+1,c_0+1,c_1-1} &(s_{i+1}=0) \\ f_{i+1,c_0-1,c_1+1} &(s_{i+1}=1) \\ f_{i+1,c_0+1,c_1} &(s_{i+1}=0\ \operatorname{or}\ s_{i+1}=0) \\ f_{i+1,c_0,c_1+1} &(s_{i+1}=1\ \operatorname{or}\ s_{i+1}=1) \end{cases} \]

考虑计算后面加入 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 后能够得到多少种不同的方案，令 \(g_{i,c_0,c_1}\) 表示 \(i\) 后面加入 \(c_0\) 个 \(0\) 和 \(c_1\) 个 \(1\) 后能够得到多少种不同的方案。

考虑将连续的一段 \(0\)，如果在这段中插入 \(0\) 时我们强制它插在开头，那么就可以转移了：

\[g_{i,c_0,c_1}\to \begin{cases} g_{i-1,c_0,c_1} \\ g_{i,c_0,c_1+1} &(s_{i}=0) \\ g_{i,c_0+1,c_1} &(s_{i}=1) \end{cases} \]

记得需要将空串的情况去掉。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=305;
const int MOD=998244353;
int n;
char s[N];
long long dp[N][N][N];
bool f[N][N][N];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	dp[n][0][0]=1;
	for(int i=n;i>=1;i--)
		for(int c0=0;c0<i;c0++)
			for(int c1=0;c0+c1<i;c1++)
			{
				dp[i-1][c0][c1]=(dp[i-1][c0][c1]+dp[i][c0][c1])%MOD;
				if(s[i]=='0') dp[i][c0][c1+1]=(dp[i][c0][c1+1]+dp[i][c0][c1])%MOD;
				else if(s[i]=='1') dp[i][c0+1][c1]=(dp[i][c0+1][c1]+dp[i][c0][c1])%MOD;
			}
	f[0][0][0]=true;
	for(int i=0;i<=n;i++)
		for(int c0=0;c0<=i;c0++)
			for(int c1=0;c0+c1<=i;c1++)
			{
				if(i+1<=n)
				{
					f[i+1][c0][c1]|=f[i][c0][c1];
					if(s[i+1]=='0'&&c1>0) f[i+1][c0+1][c1-1]|=f[i][c0][c1];
					if(s[i+1]=='1'&&c0>0) f[i+1][c0-1][c1+1]|=f[i][c0][c1];
				}
				if(i+2<=n)
				{
					if(s[i+1]=='0'||s[i+2]=='0') f[i+2][c0+1][c1]|=f[i][c0][c1];
					if(s[i+1]=='1'||s[i+2]=='1') f[i+2][c0][c1+1]|=f[i][c0][c1];
				}
			}
	f[n][0][0]=false;
	long long ans=0;
	for(int i=0;i<=n;i++)
		for(int c0=0;c0<=i;c0++)
			for(int c1=0;c0+c1<=i;c1++)
				if(f[i][c0][c1]) ans=(ans+dp[i][c0][c1])%MOD;
	printf("%lld",ans);
	return 0;
}

E - Permutation Cover

考虑最后的序列肯定是若干个排列相交的情况，考虑如果有一个点同时被多个排列同时覆盖，我们只需要考虑其中的两个排列。

考虑两个排列相交的情况，将某个数放在相交部分，它对当前这个数的个数的贡献为 \(1\)，否则的贡献为 \(2\)。

那么可以看出答案为无解的情况为

\[\max(a_i)\ge 2\cdot \min(a_i)+1 \]

否则一定可以构造出方案，具体证明的话看官方题解去吧。

考虑新插入某些数，枚举当前插入数的长度，贪心地构造方案：

  • 当 \(\max(a_i)\le 2\cdot \min(a_i)\) 时，直接贪心将字典序最小的加入目前的答案串。
  • 当 \(\max(a_i)= 2\cdot \min(a_i)+1\) 时，需要满足所有的 \(\max(a_i)\) 的位置都在 \(\min(a_i)\) 之前。
  • 当 \(\max(a_i)> 2\cdot \min(a_i)+1\) 时，无法构造方案。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int K=105,N=1005;
int k,n;
int a[K];
vector<int>merge(const vector<int>&a,const vector<int>&b)
{
	vector<int>res;
	size_t i=0,j=0;
	while(i<a.size()&&j<b.size())
	{
		if(a[i]<b[j]) res.push_back(a[i]),i++;
		else res.push_back(b[j]),j++;
	}
	while(i<a.size())
		res.push_back(a[i]),i++;
	while(j<b.size())
		res.push_back(b[j]),j++;
	return res;
}
int ans[N],tot;
int b[K];
bool pos[K];
vector<int>add(int len)
{
	for(int i=1;i<=k;i++)
		pos[i]=false,b[i]=a[i];
	vector<int>pre;
	for(int i=tot,j=1;i>=1&&j<=k-len;i--,j++)
		pre.push_back(ans[i]);
	for(int u:pre)
		pos[u]=true;
	for(int i=1;i<=k;i++)
		if(!pos[i]) b[i]--;
	for(int i=1;i<=k;i++)
		if(b[i]<0) return {k+1};
	int Min=*min_element(b+1,b+k+1),Max=*max_element(b+1,b+k+1);
	if(Min*2>=Max)
	{
		vector<int>res;
		for(int i=1;i<=k;i++)
			if(!pos[i]) res.push_back(i);
		return res;
	}
	else if(Min*2+1==Max)
	{
		vector<int>x,y;
		for(int i=1;i<=k;i++)
			if(!pos[i]&&b[i]==Max) x.push_back(i);
		for(int i=1;i<=k;i++)
			if(!pos[i]&&b[i]==Min) x.push_back(i);
		for(int i=1;i<=k;i++)
			if(!pos[i]&&b[i]!=Min&&b[i]!=Max) y.push_back(i);
		vector<int>res=merge(x,y);
		pre.insert(pre.end(),res.begin(),res.end());
		int L=0,R=(int)(pre.size())-1;
		for(int i=0;i<pre.size();i++)
		{
			if(b[pre[i]]==Max) L=max(L,i);
			if(b[pre[i]]==Min) R=min(R,i);
		}
		if(L<R) return res;
		else return {k+1};
	}
	else return {k+1};
}
void solve()
{
	vector<int>res={k+1};
	for(int len=1;len<=k&&tot+len<=n;len++)
	{
		int d=k-len;
		if(tot-d>=0)
		{
			vector<int>now=add(len);
			res=min(res,now);
		}
	}
	for(int u:res)
	{
		ans[++tot]=u;
		a[u]--;
		printf("%d ",u);
	}
	return;
}
int main()
{
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
		scanf("%d",&a[i]),n+=a[i];
	int Min=*min_element(a+1,a+k+1),Max=*max_element(a+1,a+k+1);
	if(2*Min+1<=Max)
	{
		printf("-1");
		return 0;
	}
	while(tot<n)
		solve();
	return 0;
}

F - Forbidden Tournament

考虑将原图缩点，缩完点以后的图一定是一个链状 DAG。可以发现，最多只有一个强联通分量的点的个数大于等于 \(3\)，其他最多只有一个点。

可以枚举强联通分量的个数，那么我们只需要求出点数等于 \(n-i\)，度数小于等于 \(k-i\) 的强联通图的方案数，最后乘上 \(P_{n}^i\) 就是了。

考虑计算满足条件的强联通图的方案数，不妨选一个点 \(1\)，将它的所有的入度和出度分为两个集合 \(X,Y\)，可以发现 \(X,Y\) 都是链状 DAG。

不妨将 \(X,Y\) 中的点 \(x_1,x_2,\cdots ,x_n\) 和 \(y_1,y_2,\cdots ,y_m\) 按照拓扑序排序。显然必有 \(y_m\to x_1\) 的边。可以发现，从 \(y_b\) 连向 \(x_i\) 的边必然是一个前缀，且那个分界点具有单调性。

那么就可以将问题转化到网格上，大概是一个折线计数问题，还要考虑 \(k\) 的限制，大概就是两条斜线限制一下，将路径上方的点染成黑色，其他为白色。令 \(f_{i,j}\) 表示第 \(i\) 行有 \(j\) 个黑点的方案数，DP 一下即可。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=205;
int n,k,p;
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p,b>>=1;
	}
	return res;
}
long long fac[N],inv[N];
void init(int n=200)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%p;
	inv[n]=ksm(fac[n],p-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%p;
	return;
}
long long P(int n,int m)
{
	if(m>n) return 0;
	return fac[n]*inv[n-m]%p;
}
long long f[N][N];
long long sum[N][N];
int calc(int n,int m,int k)
{
	f[0][m]=1;
	for(int i=1;i<=m-1;i++)
		f[0][i]=0;
	f[0][0]=-1;
	for(int j=0;j<=m;j++)
	{
		sum[0][j]=j>0?sum[0][j-1]:0;
		sum[0][j]=(sum[0][j]+f[0][j]+p)%p;
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			f[i][j]=0;
			if(i-1+j<=k&&n-i+m-j<=k)
			{
				f[i][j]=(f[i][j]+(sum[i-1][m]-(j>0?sum[i-1][j-1]:0)+p)%p)%p;
			}
			sum[i][j]=j>0?sum[i][j-1]:0;
			sum[i][j]=(sum[i][j]+f[i][j])%p;
		}
	return f[n][0];
}
long long solve(int n,int k)
{
	if(n==1) return 1;
	long long res=0;
	for(int deg=2;deg<n;deg++)
		res=(res+calc(deg,n-deg,k))%p;
	return res*fac[n-1]%p;
}
int main()
{
	scanf("%d%d%d",&n,&k,&p);
	init();
	long long ans=0;
	for(int i=0;i<=k;i++)
		ans=(ans+P(n,i)*solve(n-i,k-i)%p)%p;
	printf("%lld",ans);
	return 0;
}