2023.8.16模拟赛总结

董哲仁 / 2023-08-16 / 原文

T1 Idiot 的乘幂

题目大意就是给\(a,b,c,d,p\)满足

求解

这题考场一开始发现\(\gcd(a,c)=1\)没啥用，后来发现其实很巧妙，直接辗转相除\(a,c\)同时维护\(\chi^a,\chi^c\)最后剩下来的就是\(\chi\)

当然题解给了一个鬼才想到的做法构造\(\chi =\chi^1=\chi^{ax+cy}\)

所以可以用exgcd求解方程

\[ax+cy=1 \]

然后直接用\(\chi=b^xd^y\)求解就行了。

#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
LL fpow(LL a,LL b,LL P){LL ret=1; 
	for(;b;b>>=1,a=a*a%P)
	if(b&1)ret=ret*a%P;
	return ret;
}
LL exgcd(LL a,LL b,LL &x,LL &y){
	if(b==0)return x=1,y=0,a;
	LL d=exgcd(b,a%b,y,x);
	return y=y-a/b*x,d;
}
LL inv(LL x,LL P){
	LL ret,kth;
	exgcd(x,P,ret,kth);
	return (ret%P+P)%P;
}
LL solve(LL a,LL b,LL ib,LL c,LL d,LL id,LL P){
	if(c==0)return b;
	return solve(c,d,id,a%c,b*fpow(id,a/c,P)%P,ib*fpow(d,a/c,P)%P,P); 
}
int main(){
	int T;scanf("%lld",&T);
	while(T--){
		LL a,b,c,d,P;
		scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&P);
		if(fpow(b,c,P)!=fpow(d,a,P)){
		puts("No Solution!");continue;}
		LL ans=solve(a,b,inv(b,P),c,d,inv(d,P),P);
		if(fpow(ans,a,P)==b&&fpow(ans,c,P)==d)
		printf("%lld\n",ans);
		else puts("No Solution!");
	}
	return 0;
}

T2 小 D 与原题

大意说构造\(n-1\)组，每组\(\frac n 2\)个点对，使得每组里用的数不同，\(n-1\)组里使用的所有点对不相同

这个题一眼淼题，再看一眼就会爆炸发现不简单，他要求每次\(\frac n2\)题使用的原题不能相同，当然在一小时思考后想出了正解。

考虑把点从\(0\)到\(n-1\)标号，我们使第\(x+1\)组匹配包含满足\(i+j\equiv x(\mod n-1)\)的边\((i,j)\)和一条边\((p,n-1)\)满足\(2p\equiv x(\mod n-1)\)就可以了，正确性可以保证

#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
const int N=1005;
int n;
bool flag[N][N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++,putchar(10))
	for(int j=1;j<n;j++){
		int k=(n-1-j+i)%(n-1)+1;
		if(k==j)k=n;
		if(j!=k&&!flag[j][k]){
			printf("%d %d ",j,k);
			flag[j][k]=flag[k][j]=1;
		}
	}
	return 0;
}

T3 小 D 与随机

大意说给一棵树，定义好点为一个点权值是这个点到根的链上所有节点权值的最大值，每个节点的权值为1到n，且两两不同，好点个数为\(c\)，求\(k^c\)的总和

考场，考虑水分，观察到有\(40\%\)的链，直接dp，这里很滑稽，20分暴力不会写写了个40分的链。

设状态\(f_i\)表示前\(i\)个答案的总和，因为如果第\(i\)个点是好点那么对于前\(i\)个节点来说它只有一种选法，如果\(i\)个点不是好点的话它不能选最大的所以有\(i-1\)种选法，可得转移

\[f_i=kf_{i-1}+(i-1)f_{i-1} \]

那么现在考虑正解，我们把树上的好点染成黑点，其他为白点

设\(f_{i,j}\)为以\(i\)为根的子树中有\(j\)个黑点的期望，先用树形背包转移出在\(i\)子树中不计\(i\)节点的\(f\)值。

然后分类讨论

若\(i\)节点为黑点那么，显然的概率为\(\frac 1{j+1}\)有转移\(F_j=F_j+\frac{kf_{i,j}}{j+1}\)
若\(i\)节点为白点，我们可以容斥一波，先加上当前点随便黑白的期望，再减去当前节点为黑点的期望，发现\(F_j=F_j+f_{i,j}-f_{i,j-1}\)

综合一下转移即可

#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
const int N=5005;
const LL mod=998244353;
LL fac[N+5],inv[N+5];
LL fpow(LL a,LL b){LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
	if(b&1)ret=ret*a%mod;
	return ret;
}
void init(){fac[0]=1;
	for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;
	inv[N]=fpow(fac[N],mod-2);
	for(int i=N;i;i--)inv[i-1]=inv[i]*i%mod;
}
LL Inv(LL x){return inv[x]*fac[x-1]%mod;}

struct Edge{int Nxt,To;}Ed[N<<1];
int Head[N],Cnt;
void Add(int u,int v){
	Ed[++Cnt]={Head[u],v};
	Head[u]=Cnt;
}

LL f[N][N],F[N],K;
int sze[N];
void add(LL &x,LL y){x=(x+y+mod)%mod;}
void Dfs(int u,int fa){
	f[u][0]=1;
	for(int i=Head[u],v;i;i=Ed[i].Nxt)
	if((v=Ed[i].To)!=fa){
		Dfs(v,u);
		for(int j=0;j<=sze[u];j++)
		for(int k=0;k<=sze[v];k++)
		add(F[j+k],f[u][j]*f[v][k]%mod);
		sze[u]+=sze[v];
		for(int j=0;j<=sze[u];j++)
		f[u][j]=F[j],F[j]=0;
	}
	for(int i=0;i<=sze[u];i++){
		add(F[i+1],f[u][i]*K%mod*Inv(i+1)%mod);
		if(fa)add(F[i],f[u][i]),add(F[i+1],-f[u][i]);
	}
	sze[u]++;
	for(int i=0;i<=sze[u];i++)f[u][i]=F[i],F[i]=0;
}
int main(){
	init();
	int n;
	scanf("%d%lld",&n,&K);
	for(int i=1,u,v;i<n;i++)
	scanf("%d%d",&u,&v),Add(u,v),Add(v,u); 
	Dfs(1,0);
	LL ans=0;
	for(int i=1;i<=n;i++)add(ans,f[1][i]);
	printf("%lld",ans*fac[n]%mod);
	return 0;
}

T4 小 D 与游戏

这题考场没交，没啥想法。

题目大意是说一个由a,b,c组成的字符串，每次可以选两个相邻且不同的字符，把这两个字符改成另外一个字符

直接上正解，该题有以下结论

首先考虑把a,b,c分别设为0,1,2，那么会发现每次修改，字符串的每位之和前后是相同的
然后是最终串必然至少有两个相邻的相同字符（除非初始串相邻两两不同然后不操作）
最后是只要满足以上两条的字符串都可以构造出来（最为离谱，不会证）

这题的三个结论对于\(|S|\le 3\)不适用，所以可以打表

最后特判一下初始相邻两两不同的情况，答案++，和字符全相同直接输出1即可

#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
const int N=2e5+5;
const LL mod=998244353;
char ch[N];
int a[N];
LL f[N][3][3][2];
LL add(LL &x,LL y){x+=y,x%=mod;}
int main(){fre(game);
	cin>>ch+1;
	int n=strlen(ch+1),m=0;
	for(int i=1;i<=n;i++)
	a[i]=ch[i]-'a',m+=a[i],m%=3;
	if(n==1)return puts("1"),0;
	if(n==2)return puts(a[1]==a[2]?"1":"2"),0;
	if(n==3){
		if(a[1]==a[2]&&a[2]==a[3])puts("1");
		else if(a[1]==a[2]||a[2]==a[3])puts("6");
		else if(a[1]==a[3])puts("7");
		else puts("3");
		return 0;
	}
	f[1][0][0][0]=f[1][1][1][0]=f[1][2][2][0]=1;
	for(int i=2;i<=n;i++)
	for(int j=0;j<=2;j++)
	for(int k=0;k<=2;k++)
	for(int w=0;w<=2;w++){
		if(j!=k||i==1)
		add(f[i][j][(w+j)%3][1],f[i-1][k][w][1]),
		add(f[i][j][(w+j)%3][0],f[i-1][k][w][0]);
		else 
		add(f[i][j][(w+j)%3][1],f[i-1][k][w][1]),
		add(f[i][j][(w+j)%3][1],f[i-1][k][w][0]);
	}
	LL ans=0;bool flag1=1,flag2=1;
	for(int i=1;i<n;i++)if(a[i]!=a[i+1]){flag1=0;break;}
	for(int i=1;i<n;i++)if(a[i]==a[i+1]){flag2=0;break;}
	for(int i=0;i<=2;i++)ans=(ans+f[n][i][m][1])%mod;
	printf("%lld",flag1?1:(ans+flag2));
	return 0;
}