2023.7.3测试

标签：return int LL times step 2023.7 测试 MOD

T1 边的方向

一个无重边、自环的无向图，现在给每条边标上方向，要求每个点有且只有一条出边，求有多少种合法的方案，答案模 \(998244353\)

\(1\leq n,m\leq 2\times 10^5\)

不算很难的题

若 \(m<n\) 或者存在度数为 \(0\) 的点直接输出 \(0\)

之后把所有度数为 \(1\) 的点的边全部标好方向并删掉，剩下一些存在环的图

如果环里套环，即某个点的度数不为 \(2\)，那么就输出 \(0\)，否则记 \(cnt\) 为环的个数，答案就为 \(2^{cnt}\)

#include<bits/stdc++.h>
#define LL long long
#define mp make_pair
using namespace std;

const int N=200010;
const LL MOD=998244353;

int n,m,deg[N],cnt;
vector < pair<int,int> > g[N];
bool e[N],flag[N],vis[N];
LL ans=1;

void dfs(int x)
{
	vis[x]=1;
	for(int i=0; i<g[x].size(); i++)
	{
		if(!e[g[x][i].second])
		{
			int y=g[x][i].first;
			if(!vis[y] && !flag[y])
				dfs(y);
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(mp(y,i));
		g[y].push_back(mp(x,i));
		deg[x]++;  deg[y]++;
	}
	
	if(m<n)
	{
		printf("0");
		return 0; 
	}
	
	for(int i=1; i<=n; i++)
	{
		if(!deg[i])
		{
			printf("0");
			return 0;
		}
	}
	
	for(int i=1; i<=n; i++)
	{
		if(deg[i]==1)
		{
			int x=i;
			do
			{
				int y=0,z=0;
				for(int j=0; j<g[x].size(); j++)
				{
					if(!e[g[x][j].second])
					{
						y=g[x][j].first;  z=g[x][j].second;
						break;
					}	
				}
				
				deg[x]--;  deg[y]--;
				e[z]=1;  flag[x]=1;
				if(deg[y]==0 && !flag[y])
				{
					printf("0");
					return 0;
				}
				x=y;
			}while(deg[x]==1);
		}
	}
	
	for(int i=1; i<=n; i++)
	{
		if(!flag[i] && deg[i]!=2)
		{
			printf("0");
			return 0;
		}
	}
	
	for(int i=1; i<=n; i++)
	{
		if(!flag[i] && !vis[i])
			dfs(i),cnt++;	
	}
	
	for(int i=1; i<=cnt; i++)
		(ans*=2)%=MOD;
		
	printf("%lld",ans);
	
	return 0;
}

T2 游戏得分

有长度为 \(n\) 的数组 \(a\) 满足 \(a_i=i\)。设 \(p\) 是 \(1\cdots n\) 的某个排列，现在重复操作：令 \(a_{p_i}=a_i\)，直到 \(a\) 恢复到原来 \(a_i=i\) 的样子，记操作次数为 \(x\)。那么该排列的得分 \(f(p)=x^k\)，其中 \(k\) 是输入的。对于所有 \(1\cdots n\) 的所有排列 \(p\)，求它们的得分之和即 \(\sum{f(p)}\)。答案模 \(998244353\)

\(2\leq n\leq 50\)，\(1\leq k\leq 10000\)

考场上努力搞出来了（被薄纱）

首先可感觉到排列的变换过程中会存在一些分组，组内的数字不断交换，但组与组之间没有联系。而每个组内部一次循环所需的操作数是数字的个数，最后的操作次数就是所有组操作次数的最小公倍数

由于数据比较小，所以我们可以暴力地从大到小去递归枚举组内的数字数量。记状态 \(f(step,s,pre,cur)\) 表示当前枚举到的组内数字数量为 \(step\)，当前还有 \(s\) 个数字没有被分组，前面分组产生的贡献为 \(pre\)，当前最小公倍数为 \(cur\)。

那么，我们枚举分组的组数 \(i\)，则此次分组产生的贡献为

\[\binom{s}{i\times step}\times \frac{\prod\limits_{j=1}^{i}{\binom{j\times step}{step}}}{i!}\times \left((step-1)!\right)^i \]

更新 \(pre\) 和 \(cur\) 把它带到下一层去，在 \(step=0\) 时用 \(pre\times cur^k\) 更新答案即可

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=60;
const LL MOD=998244353;

int n,a[N];
LL k,ans,tot[N],fac[N],inv[N];
bool v[N];

LL gcd(LL a,LL b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}

LL lcm(LL a,LL b)
{
	return a*b/gcd(a,b);
}

LL ksm(LL x,LL y)
{
	LL res=1;
	while(y)
	{
		if(y&1)
			res=res*x%MOD;
		x=x*x%MOD;
		y>>=1;
	}
	
	return res;
}

void prework()
{
	fac[0]=inv[0]=1;
	for(int i=1; i<=n; i++)
	{
		fac[i]=(fac[i-1]*i)%MOD;
		inv[i]=ksm(fac[i],MOD-2);
	}
}

LL C(int x,int y)
{
	if(y>x)
		return 0;
	return fac[x]*inv[x-y]%MOD*inv[y]%MOD;	
}

LL count(int t,int x)
{
	LL res=1;
	for(int i=t*x; i>=x; i-=x)
		(res*=C(i,x))%=MOD;
	(res*=inv[t])%=MOD;
	
	return res;
}

void dfs(int step,int s,LL pre,LL cur) //step枚举到的层数，s现在还有多少人，pre之前的贡献，cur当前最小公倍数 
{
	if(s==0)
	{
		(ans+=1LL*pre*ksm(cur,k)%MOD)%=MOD;
		return;
	}
	if(step==0)
		return;
	
	for(int i=0; i*step<=s; i++)
		dfs(step-1,s-i*step,pre*count(i,step)%MOD*ksm(fac[step-1],i)%MOD*C(s,i*step)%MOD,lcm(cur,i==0?cur:(LL)step));
}

int main()
{
	scanf("%d%lld",&n,&k);
	
	prework();
	
	dfs(n,n,1,1);
	
	printf("%lld",ans);
	
	return 0;
}

T3 Group Projects

又又又是插入 \(\rm dp\)！！！

显然要排序（~~我也不知道怎么显然~~），将 \(a_i\) 从小到大排序。因为我们不关注具体如何分组，只关心差值是多少，所以排完序是有利于我们去计算贡献的

状态的第一维显然是考虑到第 \(i\) 个数，还是考虑将 \(a_i\) 插入到前面的额某个组中，所以我们第二维状态可以记还有多少个组是不完整的（即可被插入），当然我们还要用第三维来记录当前的“不和谐度”之和

将 \(a\) 丢到数轴上理解，显然新加入的 \(a_i\) 会对之前不完整的组造成影响，产生 \((a_i-a_{i-1})\times j\) 的贡献，\(j\) 为组数，我们这这里费用提前计算，当后面的数字插入时就无需考虑插入到哪一个组里。记 \(p=(a_i-a_{i-1})\times j\)，下面我们分类讨论：

当 \(a_i\) 单独成组时

\(f[i-1][j][k]\rightarrow f[i][j][k+p]\)
当 \(a_i\) 作为组的中间时，可以随便选一个插入

\(f[i-1][j][k]\times j \rightarrow f[i][j][k+p]\)
当 \(a_i\) 作为一个组的结尾时，组数会 \(-1\)

\(f[i-1][j][k]\times j\rightarrow f[i][j-1][k]\)
当 \(a_i\) 作为一个组的开头时，组数要 \(+1\)

\(f[i-1][j][k]\rightarrow f[i][j+1][k]\)

#include<bits/stdc++.h>
using namespace std;

const int N=210,M=1010;
const int MOD=1e9+7;

int n,m,a[N],f[N][N][M];

int main() 
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
		
	sort(a+1,a+1+n);
	
	f[0][0][0]=1;
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=n; j++)
		{
			int p=(a[i]-a[i-1])*j;
			for(int k=0; k+p<=m; k++)
			{
				(f[i][j][k+p]+=1LL*f[i-1][j][k]*(j+1)%MOD)%=MOD;
				if(j!=n)
					(f[i][j+1][k+p]+=f[i-1][j][k])%=MOD;
				if(j!=0)
					(f[i][j-1][k+p]+=1LL*f[i-1][j][k]*j%MOD)%=MOD;
			}
		}
	}
	
	int ans=0;
	for(int i=0; i<=m; i++)
		(ans+=f[n][0][i])%=MOD;
	
	printf("%d",ans);
	
	return 0;
}

T4 卡片查看测评数据信息

有 \(3n\) 张卡片从左往右排成一行，第 \(i\) 张卡片写有一个整数 \(a[i]\)，代表这个卡片的价值，其中 \(1<=a[i]<=n\)。

重复以下操作 \(n-1\) 次：

1、针对当前剩下的卡片，你可以对最左边的 \(5\) 张卡片任意调整次序，调整结束后，若最左边的 \(3\) 张卡片的价值相同，那么你的得分会增加 \(1\)。

2、最左边的 \(3\) 张卡片会被删除。

若最终剩下的 \(3\) 张卡片的价值相同，你得分再增加 \(1\) 分。

输出最大总得分。

输出 \(n\) 喜提 \(9\) 分

\(100+100+0+9=209\)，\(\rm rk 8\)

标签：return,int,LL,times,step,2023.7,测试,MOD
From： https://www.cnblogs.com/xishanmeigao/p/17612588.html

T1 边的方向

T2 游戏得分

T3 Group Projects

T4 卡片查看测评数据信息

相关文章

赞助商

阅读排行

2023.7.3测试

T1 边的方向

T2 游戏得分

T3 Group Projects

T4 卡片 查看测评数据信息

相关文章

赞助商

阅读排行

T4 卡片查看测评数据信息