首页 > 其他分享 >省选联测31

省选联测31

时间:2023-02-13 19:48:13浏览次数:42  
标签:tar 省选 31 int maxn 联测 now Rep Mod

A.西克

赛时冲了四个小时,在下行部分假了无数个做法。
暴力两个log的话就倍增走一条重链,然后切重链,来回操作就行了。

题解

image
image

点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=2e6+10;

int A[maxn],B[maxn];
int n,q;

struct QQ{ int x,y,lf; }Q[maxn>>1];
int Ans[maxn>>1];
int nxt[maxn];

struct Graph{
	struct eg{ int to,next; }e[maxn];
	int len,head[maxn];
	void lqx(int from,int to)
	{ e[++len].to=to,e[len].next=head[from],head[from]=len; }
	int f[maxn][22];set<pii>S[maxn];
	int dep[maxn],son[maxn],siz[maxn],top[maxn],fa[maxn],dfn[maxn],rk[maxn],Te;
	void Dfs1(int u){
		dep[u]=dep[fa[u]]+1;siz[u]=1;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			fa[v]=u;Dfs1(v);siz[u]+=siz[v];
			if(!son[u] || siz[v]>siz[son[u]])son[u]=v;
		}
	}
	void Dfs2(int u,int tp){
		top[u]=tp;dfn[u]=++Te;rk[Te]=u;
		S[top[u]].insert( pii(A[u],dfn[u]) );
		if(son[u])Dfs2(son[u],tp);
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;if(v==son[u])continue;
			Dfs2(v,v);
		}
	}
	int Lca(int u,int v){
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]])swap(u,v);
			u=fa[top[u]];
		}
		return dep[u] < dep[v] ? u : v;
	}
	void Build1(int u){
		if(nxt[B[u]]){
			f[u][0]=nxt[B[u]];
			Rep(i,1,21)f[u][i]=f[f[u][i-1]][i-1];
		}
		int tmp=nxt[A[u]];nxt[A[u]]=u;
		for(int i=head[u];i;i=e[i].next)Build1(e[i].to);
		nxt[A[u]]=tmp;
	}
	int Up(int u,int lf){
		Dwn(i,21,0)if(dep[f[u][i]]>=dep[lf])u=f[u][i];
		return u;
	}
	int Col(int u,int lf,int c){
		int res=0;
		while(top[u]!=top[lf]){
			auto it = S[top[u]].lower_bound( pii(c,0) );
			if(it!=S[top[u]].end() && it->fir==c && it->sec<=dfn[u])res=rk[it->sec];
			u=fa[top[u]];
		}
		auto it = S[top[u]].lower_bound( pii(c,dfn[lf]) );
		if(it!=S[top[u]].end() && it->fir==c && it->sec<=dfn[u])res=rk[it->sec];
		return res;
	}
	int Sol(int u,int v,int lf){
		int res=A[u];
		while(u!=lf){ if(res==A[u])res=B[u]; u=fa[u]; }
		if(res==A[lf])res=B[lf];
		vector<int>vec;
		while(v!=lf)vec.emplace_back(v),v=fa[v];
		reverse(vec.begin(),vec.end());
		for(auto it : vec)if(res==A[it])res=B[it];
		return res;
	}
	void Build2(int u){
		vector<int>vec;for(int i=u;i;i=son[i])vec.emplace_back(i);
		reverse(vec.begin(),vec.end());
		for(auto it : vec){
			if(nxt[B[it]]){
				f[it][0]=nxt[B[it]];
				Rep(i,1,21)f[it][i]=f[f[it][i-1]][i-1];
			}else Rep(i,0,21)f[it][i]=0;
			nxt[A[it]]=it;
		}
		for(auto it : vec)nxt[A[it]]=0;
	}
	int Jump(int u,int v){
		vector<int>vec;vec.emplace_back(v);	
		while(top[u]!=top[v])v=fa[top[v]],vec.emplace_back(v);
		while( vec.size() ){
			Dwn(i,21,0)if(f[u][i] && dep[f[u][i]]<=dep[vec.back()])u=f[u][i];
			vec.pop_back();
			while(!vec.empty()){
				int tmp=Col(vec.back(),u,B[u]);
				if(tmp){u=tmp;break; }
				vec.pop_back();
			}
		}
		return B[u];
	}
}G;

unsigned int S1,S2;
unsigned int rnd(){
	S1*=S2,S2>>=S1&13,S2-=S1,S1^=S2;
	return ((S1-S2)&(S1+S2))^(S1*S2>>4);
}

void READ(){
	cin>>n>>q>>S1>>S2;
	if(n<=500000){
		int x;
		Rep(i,1,n)cin>>A[i]>>B[i];
		Rep(i,2,n){ cin>>x;G.lqx(x,i); }
		Rep(i,1,q)cin>>Q[i].x>>Q[i].y; 
	}else{
		int x;
		Rep(i,1,500000)cin>>A[i]>>B[i];
		Rep(i,500001,n){
			A[i]=rnd()%n+1;B[i]=A[rnd()%500000+1];
			if(A[i]==B[i]){ ++A[i]; if(A[i]>n)A[i]=1; }
		}
		Rep(i,2,n){ cin>>x;G.lqx(x,i); }
		Rep(i,1,q)cin>>Q[i].x>>Q[i].y;
	}
}

void solve(){
	READ();G.Dfs1(1),G.Dfs2(1,1);
	bool flag=true;
	Rep(i,1,q)Q[i].lf=G.Lca(Q[i].x,Q[i].y),flag&=(Q[i].y==Q[i].lf);
	G.Build1(1);Rep(i,1,q)Q[i].x=G.Up(Q[i].x,Q[i].lf);
	Rep(i,1,q){ 
		int p=G.Col(Q[i].y,Q[i].lf,B[Q[i].x]);
		Ans[i]=B[Q[i].x];if(p)Q[i].x=p,Q[i].lf=p;else Q[i].x=0; 
	}
	memset(nxt,0,sizeof(nxt));
	Rep(i,1,n)if(G.top[i]==i)G.Build2(i);
	Rep(i,1,q)if(Q[i].x)Ans[i]=G.Jump(Q[i].x,Q[i].y);
	//Rep(i,1,q)cout<<Ans[i]<<"\n";
	int ans=0;
	Rep(i,1,q)ans^=Ans[i];
	cout<<ans<<"\n";
}

int main (){
	fre(shik);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; 
}

B.尼特

粘题解了

题解

image

image

只写到了n方
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=5e3+10,Mod=998244353;

int pw(int x,int p){int res=1,base=x;while(p){if(p&1)res=1LL*res*base%Mod;base=1LL*base*base%Mod;p>>=1;}return res;}
int Inv(int x){return pw(x,Mod-2);}

int a[maxn],b[maxn];
int n,m,ans;
int f[2][maxn],g[2][maxn];

void solve(){
	cin>>n>>m;Rep(i,1,n)cin>>a[i];
	f[0][0]=1;int now=0;
	Rep(i,1,n-1){
		int tar=now^1;memset(f[tar],0,sizeof(f[tar]));memset(g[tar],0,sizeof(g[tar]));
		Rep(j,0,i){
			if(a[i]==a[i+1]){
				f[tar][j]=(f[tar][j]+1LL*f[now][j]*(m-1))%Mod;
				g[tar][j]=(g[tar][j]+1LL*g[now][j]*(m-1))%Mod;
				f[tar][j]=(f[tar][j]+f[now][j])%Mod;
				g[tar][j]=(0LL + g[tar][j]+g[now][j]+f[now][j])%Mod;
			}else{
				f[tar][j]=(f[tar][j]+1LL*f[now][j]*(m-2))%Mod;
				g[tar][j]=(g[tar][j]+1LL*g[now][j]*(m-2))%Mod;
				f[tar][j+1]=(f[tar][j+1]+f[now][j])%Mod;
				g[tar][j+1]=(0LL + g[tar][j+1]+g[now][j]+f[now][j])%Mod;
				if(j==0){
					f[tar][j]=(f[tar][j]+f[now][j])%Mod;
					g[tar][j]=(0LL + g[tar][j]+g[now][j]+f[now][j])%Mod;
				}else{
					f[tar][j-1]=(f[tar][j-1]+1LL*f[now][j])%Mod;
					g[tar][j-1]=(g[tar][j-1]+1LL*g[now][j])%Mod;
				}
			}
		}
		now^=1;
	}
	int ans=0;
	Rep(i,0,n)ans=(ans+g[now][i])%Mod;
	cerr<<ans<<"\n";
	cout<<1LL*ans*Inv(pw(m,n-1))%Mod<<"\n";
}

int main (){ fre(nit);ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }

C.苯为

很容易看出只需要算出环的方案数就有办法处理了,在环上k着色的方案数是

\[(k-1)^n + (-1)^n(k-1) \]

求教了大佬,有色多项式加二项式反演推出来的,有递推解通项的。

把非环点的贡献也乘进去,化简一下就很好做了。

题解

image
image

点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
#define int ll
using namespace std;

const int maxn=1e6+10,Mod=421969921;

int pw(int x,int p){int res=1,base=x;while(p){if(p&1)res=1LL*res*base%Mod;base=1LL*base*base%Mod;p>>=1;}return res;}
int Inv(int x){return pw(x,Mod-2);}

int n,A,K;
int ans,Pw[maxn];

struct Graph{
	struct eg{ int from,to,next; }e[maxn*2];
	int len,head[maxn];
	void lqx(int from,int to)
	{ e[++len].from=from,e[len].to=to,e[len].next=head[from],head[from]=len; }
	int sum[maxn];
	void Dfs(int u,int fa){
		sum[u]=Pw[1];ans=(ans+Pw[1])%Mod;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;if(v==fa)continue;
			Dfs(v,u);
			ans=(ans+sum[u]*sum[v]%Mod*2LL)%Mod;
			sum[u]=(sum[u]+sum[v]*Pw[1])%Mod;
		}
	}
}G;

void solve(){
	cin>>n>>A>>K;A%=(Mod-1);K%=Mod;
	Rep(i,2,n){ int u,v;cin>>u>>v;G.lqx(u,v),G.lqx(v,u); }
	Pw[0]=1;Pw[1]=Inv(pw((1LL-K)%Mod,A+1));
	G.Dfs(1,0);
	ans=ans*pw(pw(K-1,A+1),n)%Mod*(K-1)%Mod;
	ans=(ans+(n*n%Mod)%Mod*pw(K-1,n*((A+1)%(Mod-1))%(Mod-1))%Mod)%Mod;
	ans=(ans%Mod+Mod)%Mod;
	cout<<ans<<"\n";
}

#undef int
int main (){ fre(ber);ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }

标签:tar,省选,31,int,maxn,联测,now,Rep,Mod
From: https://www.cnblogs.com/Delov/p/17117549.html

相关文章