模拟88 考试总结

2024-01-24 13:34:49

崩陨

考试经过

啥也不会，T1想了半天差点睡着，然后狂打暴力
最后出来T1dp假了，T3模数是993244853，~~根本无法评价~~
垫底了，然后自闭一天，啥也没干，旁边人切掉了\(10^9+7\)道题，我啥也不会

T1.按位或

暴力基本和正解关系不大，然而我想了一个极其复杂的\(n^3\)还假了
正解在于容斥，%%%容斥带师WYZG
假如不管3的倍数的限制，那么可以直接按照答案的位考虑，一个\(log\)轻松出结果
然而有了限制就不好玩了，发现2的若干次幂模3余数只能是1或2，那么可以用这个性质搞一下
设\(p_i\)表示至少有\(i\)位的1不选的方案数，那么是一个经典的奇加偶减的形式，答案即恰好\(0\)位不选
注意到这里并不能直接简单的组合数，因为我们还要保证所有数都是3的倍数
发现二进制下奇数位的1余数是1，偶数位的余数是2，那么可以枚举一下这\(i\)位中在奇数和偶数位的1的个数
这里又是一个\(log\)，枚举之后剩下的就可以直接随便选/不选了，我们做一个简单的dp来确定最后的方案数
\(f_{i,j}\)表示已经确定了\(i\)位，余数是\(0/1/2\)的方案数，枚举这一位选不选1转移即可
由于\(n\)个都等价所以快速幂，由于从奇数偶数位中分别要选出来，所以乘两个组合数，也很好理解
所以\(log^3\)就做完了，发现其实不难，只是脑子瓦特了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=65;
int n,t,c[N][N];
inline int ksm(int x,int y)
{
	int s=1;x%=mod;
	for(;y;y>>=1)
	{
		if(y&1)s=s*x%mod;
		x=x*x%mod;	
	}
	return s;
}
int f[N][3];
signed main()
{
	freopen("or.in","r",stdin);
	freopen("or.out","w",stdout);
	cin>>n>>t;
	int s1=0,s2=0,s=0;
	while(t)
	{
		s++;
		if(t&1)
		{
			if(s&1)s1++;
			else s2++;
		}
		t>>=1;
	}
	c[0][0]=1;
	for(int i=1;i<=64;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	int ans=0;
	for(int i=0;i<=s1+s2;i++)
	{
		int sum=0;
		for(int j=max(i-s2,(int)0);j<=s1;j++)
		{
			int p1=s1-j,p2=s2-(i-j);
			assert(p1>=0);assert(p2>=0);
			memset(f,0,sizeof(f));
			f[0][0]=1;
			for(int i=0;i<p1;i++)for(int j=0;j<=2;j++) 
			{
				f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
				f[i+1][(j+1)%3]=(f[i+1][(j+1)%3]+f[i][j])%mod;
			}
			for(int i=p1;i<p1+p2;i++)for(int j=0;j<=2;j++)
			{
				f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
				f[i+1][(j+2)%3]=(f[i+1][(j+2)%3]+f[i][j])%mod;
			}
			sum=(sum+ksm(f[p1+p2][0],n)*c[s1][j]%mod*c[s2][i-j]%mod)%mod;
		}
		if(i&1)ans=(ans-sum+mod)%mod;
		else ans=(ans+sum)%mod;
	}
	cout<<ans<<endl;
	return 0;
}

T2.最短路径

考场上根本没好好想，其实也不算很难
考虑选出\(k\)个点的最优策略，发现如果朴素一点是任选一个起点，每次走到一个点回到起点
发现不一定要每次回去，事实上应该是选择一条主路走到头，别的分叉往回走，感性理解一下
显然这个主路只走一遍，别的走两遍，那么应该选直径
因此就是任意两点距离之和2倍减去直径长度，虚树啥的咱也不懂
但题目算的期望，所以直接枚举肯定不行，考虑拆开算每条路径的贡献
对于前者，枚举每条路径，他贡献的概率就是点在两边的概率，可以用总的方案数减去不合法（点在一边）的概率
后者直接枚举直径端点，考虑另外的点能否合法从而使它成为直径
合法的条件就是不存在距离小于他，或者距离相等但是标号小
然后直接枚举就好了，乘上\(cnt-2\)选\(k-2\)的概率，\(cnt\)是合法点数，复杂度\(m^3\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2050;
const int mod=998244353;
struct node{
	int from,to,next;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{
	a[mm].from=x;a[mm].to=y;
	a[mm].next=head[x];head[x]=mm++;
}
inline int ksm(int x,int y)
{
	int s=1;x%=mod;
	for(;y;y>>=1)
	{
		if(y&1)s=s*x%mod;
		x=x*x%mod;
	}
	return s;
}
inline int ny(int x){return ksm(x,mod-2);}
int jc[N],inv[N],jcny[N],n,m,k;
inline void pre()
{
	jc[0]=jc[1]=inv[1]=jcny[0]=jcny[1]=1;
	for(int i=2;i<=n;i++)
	{
		jc[i]=jc[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		jcny[i]=jcny[i-1]*inv[i]%mod;
	}	
}
inline int C(int x,int y)
{
	if(x<y)return 0;
	if(!y)return 1;
	return jc[x]*jcny[y]%mod*jcny[x-y]%mod;
}
int d[N],fa[N],size[N],son[N],ss[N];
int top[N],ans,pp[N];bool v[N];
void dfs1(int x)
{
	v[x]=1;
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(v[y])continue;
		d[y]=d[x]+1;fa[y]=x;
		dfs1(y);size[x]+=size[y];ss[x]+=ss[y];
		ans=(ans+(1ll-((C(ss[y],k)+C(m-ss[y],k))%mod*ny(C(m,k))%mod)+mod)%mod*2%mod)%mod;
		if(size[y]>size[son[x]])son[x]=y;
	}
	size[x]++;
	ss[x]+=pp[x];
}
void dfs2(int x,int h)
{
	if(!x)return;
	v[x]=1;top[x]=h;
	dfs2(son[x],h);
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(v[y]||y==son[x])continue;
		dfs2(y,y);
	}
}
inline int getlca(int x,int y)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(d[fx]<d[fy])swap(x,y),swap(fx,fy);
		x=fa[fx],fx=top[x];
	}
	if(d[x]<d[y])swap(x,y);
	return y;
}
inline int getd(int x,int y)
{
	int lca=getlca(x,y);
	return d[x]+d[y]-2*d[lca];
}
int p[N];
signed main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)scanf("%lld",&p[i]),pp[p[i]]=1;
	sort(p+1,p+1+m);
	for(int i=1;i<n;i++)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		add(x,y);add(y,x);
	}
	pre();d[1]=1;dfs1(1);
	memset(v,0,sizeof(v));dfs2(1,1);
	for(int i=1;i<=m;i++)for(int j=i+1;j<=m;j++)
	{
		int x=p[i],y=p[j];if(x>y)swap(x,y);
		int dis=getd(x,y),sum=0;
		for(int k=1;k<=m;k++)
		{	
			int z=p[k];if(z==x||z==y)continue;
			int d1=getd(z,x),d2=getd(z,y);
			if(d1>dis||(d1==dis&&z<y))continue;
			if(d2>dis||(d2==dis&&z<x))continue;
			sum++;
		}
		ans=(ans-C(sum,k-2)*ny(C(m,k))%mod*dis%mod+mod)%mod;
	}
	cout<<ans<<endl;
	return 0;
}

T3.仙人掌

RT，不可做，咕

T4.对弈

原题P2490
发现A只会向右走，B只会向左走，那么把两个棋子看成一堆数量为\(b_i-a_i-1\)的石子，那么~~通过颓题解~~可以看出这是一个k-nim模型
结论是先手必败当且仅当所有\(a_i\)变成二进制之后每一位上的1的个数都模\(m+1\)余0，证明见下

所以可以dp，设\(f_{i,j}\)表示考虑第\(i\)位，总和为\(j\)方案数，枚举是\(m+1\)的多少倍即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100050;
const int mod=1e9+7;
int jc[N],inv[N],jcny[N],n,k,m;
int f[20][N];
inline void pre()
{
	jc[0]=jc[1]=inv[1]=jcny[0]=jcny[1]=1;
	for(int i=2;i<=n;i++)
	{
		jc[i]=jc[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		jcny[i]=jcny[i-1]*inv[i]%mod;
	}	
}
inline int C(int x,int y)
{
	if(x<y)return 0;
	if(!y)return 1;
	return jc[x]*jcny[y]%mod*jcny[x-y]%mod;
}
signed main()
{
	freopen("chess.in","r",stdin);freopen("chess.out","w",stdout);
	cin>>n>>k>>m;pre();
	f[0][0]=1;int ans=0;
	for(int i=0;i<=12;i++)for(int j=0;j<=n-k;j++)
	{	
		for(int kk=0;j+kk*(1<<i)*(m+1)<=n-k&&kk*(m+1)<=k/2;kk++)
			f[i+1][j+kk*(1<<i)*(m+1)]=(f[i+1][j+kk*(1<<i)*(m+1)]+f[i][j]*C(k/2,kk*(m+1))%mod)%mod;
	}
	for(int i=0;i<=n-k;i++)ans=(ans+f[13][i]*C(n-i-k/2,k/2)%mod)%mod;
	cout<<(C(n,k)-ans+mod)%mod<<endl;
	return 0;
}

考试总结

这场又挂没，原因是多方面的，开始节奏就乱了，到后面也没回来
希望可以尽快走出来，毕竟联赛没几天了，考场上心态一定要把握好

码农公寓