2023牛客多校7.24补题

J-Fine Logic

题意：给定n个点和m对偏序关系(x,y)，构造最少的排列数目k，使得在这k个排列中至少有一个排列满足x出现在y的前面。

分析：很考验思维的一道题，首先如果m对偏序关系不构成环，也就是一张有向无环图，于是用拓扑排序构造出一个合理排列即可。要是有环，就直接构造两个排列，一个是1<2<...<n，另一个是n<n-1<...<1。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e6+5;
const int M=4e5+5;
const int mod=998244353;
const int inf=1e9;
vector<int>q[N];
queue<int>p;
int n,m,deg[N],id[N];
void topsort(){
	int now=0;
	for(int i=1;i<=n;++i){
		if(!deg[i]){
			p.push(i);
		}
	}
	while(p.size()){
		int u=p.front();p.pop();
		id[++now]=u;
		for(int i=0;i<q[u].size();++i){
			int v=q[u][i];
			--deg[v];
			if(deg[v]==0)p.push(v);
		}
	}
	if(now<n){
		cout<<"2"<<endl;
		for(int i=1;i<=n;++i)cout<<i<<" ";cout<<endl;
		for(int i=1;i<=n;++i)cout<<n+1-i<<" ";cout<<endl;
	}
	else{
		cout<<"1"<<endl;
		for(int i=1;i<=n;++i)cout<<id[i]<<" ";
		cout<<endl;
	}
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;++i){
		int x=read(),y=read();
		q[x].push_back(y);
		++deg[y];
	}
	topsort();
	return 0;
}

B-Auspiciousness

题意：2n 张牌面数字分别为 1, 2, . . . , 2n 的牌叠放成牌堆，完成以下流程：

$\ \ \ $1.从牌堆顶取走一张牌

$\ \ \ $2.若牌堆为空则结束流程，否则猜测牌堆顶数字是否大于上一张取走的牌，并从牌堆顶取走一张牌

$\ \ \ $3.若猜测正确则回到上一步继续，否则结束流程

依照上一张牌不超过 n 则猜测牌堆顶大于上一张牌，否则猜测小于的策略猜测问对于所有可能的 (2n)! 种牌堆叠放顺序，总共能取走的牌的数量之和模 m 的结果

分析：1 ∼ n 为小数，n + 1 ∼ 2n 为大数。最终摸到牌的序列一定是小数上升序列和大数下降序列的交替，再加上最后一个不合法的数（也可能没有这个不合法的数，即摸完 2n 张牌）。设 f(i, j, k) 表示已经填了 i 个小数，j 个大数，最后一段是小/大数(k=0/1)的方案数，则\(f[i+k][j][0]=f[i+k][j][0]+f[i][j][1]*C(n-i,k)\)，\(f[i][j+k][1]=f[i][j+k][1]+f[i][j][0]*C(n-j,k)\).

上述两种转移下，对答案的贡献分别为\((i+j+k)*f[i][j][1]*C(n-i,k)*(k-1)*(2*n-i-j-k)!\)，\((i+j+k)*f[i][j][0]*C(n-j,k)*(k-1)*(2*n-i-j-k)!\)，其中\(k-1\)表示最后一段k个数有\(k-1\)种排列方式来保证这次恰好取到\(i+j+k\)个数，即在小数升序或者大数降序的基础上（仅一种情况），把前\(k-1\)个数中的任意一个移到最后而其它数保持不动。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=305;
const int M=4e5+5;
const int mod=998244353;
const int inf=1e9;
int g[N][N],f[N][N][2],jc[N<<1];
int main(){
	int T=read();
	while(T--){
		int n=read(),m=read();
		g[0][0]=1;
		for(int i=1;i<=n;++i){
			g[i][0]=1;
			for(int j=1;j<=i;++j){
				g[i][j]=(g[i-1][j]+g[i-1][j-1])%m;
			}
		}
		jc[0]=1;
		for(int i=1;i<=2*n;++i)jc[i]=(1ll*jc[i-1]*i)%m;
		int ans=0;
		for(int i=0;i<=n;++i){
			for(int j=0;j<=n;++j)f[i][j][0]=f[i][j][1]=0;
		}
		f[0][0][0]=f[0][0][1]=1;
		for(int i=0;i<=n;++i){
			for(int j=0;j<=n;++j){
				for(int k=1;k<=n-i;++k){
					f[i+k][j][0]=(f[i+k][j][0]+1ll*f[i][j][1]*g[n-i][k]%m)%m;
					ans=(ans+1ll*f[i][j][1]*g[n-i][k]%m*(i+j+k)%m*(k-1)%m*jc[2*n-i-j-k]%m)%m;
				}
				for(int k=1;k<=n-j;++k){
					f[i][j+k][1]=(f[i][j+k][1]+1ll*f[i][j][0]*g[n-j][k]%m)%m;
					ans=(ans+1ll*f[i][j][0]*g[n-j][k]%m*(i+j+k)%m*(k-1)%m*jc[2*n-i-j-k]%m)%m;
				}
				if(i==n&&j==n)ans=(ans+2ll*n%m*(f[i][j][0]+f[i][j][1])%m)%m;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}