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

省选联测27

时间：2023-02-10 06:55:05浏览次数：39  
标签：27 fa 省选 siz son int 联测 define Mod

A.神奇纸牌

比较好像的题，考虑一个数字一个数字的加，这样就变成了n个点，每个点四个01属性，有相同1属性就相连，最后是个连通图就行。

点击查看代码 
// 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=17;

int V=15,Mod;
int n;
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 g[maxn+1];

int Calc(int x){
	int res=0;
	if(x>n)return 0;
	Rep(i,0,x)
		if((x-i)&1)res=(res-pw(i,n))%Mod;
		else res=(res+pw(i,n))%Mod;
	return res;
}

int tmp[maxn],pre[maxn],suf[maxn];
int fa[maxn];
int Find(int x){ return fa[x]==x ? x : fa[x]=Find(fa[x]); }
bool Check(int x){
	Rep(i,0,V)fa[i]=i;
	Rep(i,0,V)if((x>>i)&1)tmp[i]=i;else tmp[i]=0;
	Rep(i,0,V)Rep(j,i+1,V)
		if(tmp[i]&tmp[j])fa[Find(tmp[i])]=fa[Find(tmp[j])];
	set<int>s;
	Rep(i,0,V)if(tmp[i])
		s.insert(Find(tmp[i]));
	return s.size()==1;
}

int C[maxn<<1][maxn<<1];

void Init(){
	C[0][0]=1;Rep(i,1,16){ C[i][0]=1;Rep(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod; }
	for(int i=1;i<=16;++i)g[i]=pw(i,n);
	for(int i=2;i<=16;++i){
		for(int j=1;j<i;++j)
			g[i]=(g[i]-1LL*C[i][j]*g[j])%Mod;
	}
}

void solve(){
	cin>>n>>Mod;int ans=0;
	//for(int i=1;i<=16;++i)g[i]=Calc(i),cerr<<g[i]<<"\n";
	//g[2]=2;
	Init();//Rep(i,1,16)cerr<<g[i]<<"\n";
	for(int i=1;i<(1<<16);++i)if(Check(i))
		ans=(ans+g[__builtin_popcount(i)])%Mod;
	ans=(ans+Mod)%Mod;
	cout<<(ans+1)%Mod<<"\n";
}

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

对于此题数据范围一种复杂度比较优的做法是直接枚举最终出现的属性组合的集合，判断是否达到联通，若联通则就是比较简单的有标号小球分组，就是\([ \frac{x^n}{n!}](e^x-1)^c\)，暴力二项式就完了，组合意义容斥也ok。

B.凌乱平衡树

首先一个技巧是\(\sum dep = \sum siz\)。
发现merge操作只与左树右链和右树左链有关，两边的siz形成两个单调递减的序列，贡献过程相当于维护双指针，根据题意移动一侧，并将另一侧当前位置的权加一次贡献，那么就可以用权值线段树求出每个数的贡献。rotate操作如果影响到了右/左链，那么就是在序列上添一个数或者删一个数，更新下加/删掉的数贡献即可，注意右对左有贡献，左对右也有贡献。

点击查看代码 
// 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=3e5+10;

ll ans;
int n,q;

struct Seg{
	int tr[maxn<<2];
	void Modify(int rt,int l,int r,int x,int w){
		tr[rt]+=w;if(l==r)return;
		int mid=(l+r)>>1;
		if(x<=mid)Modify(rt<<1,l,mid,x,w);
		else Modify(rt<<1|1,mid+1,r,x,w);
	}
	int Siz(int rt,int l,int r,int s,int t){
		if(s<=l && t>=r)return tr[rt];
		int mid=(l+r)>>1,res=0;
		if(s<=mid)res=Siz(rt<<1,l,mid,s,t);
		if(t>mid)res+=Siz(rt<<1|1,mid+1,r,s,t);
		return res;
	}
	int Find(int rt,int l,int r,int x){
		if(x<l || !tr[rt])return 0;
		if(l==r)return l;
		int mid=(l+r)>>1;
		if(x<=mid)return Find(rt<<1,l,mid,x);
		int tmp=Find(rt<<1|1,mid+1,r,x);
		return tmp ? tmp : Find(rt<<1,l,mid,x);
	}
}A,B;

struct Treap{
	#define lch V[p].son[0]
	#define rch V[p].son[1]
	struct Ver{ int son[2],fa,siz; }V[maxn];
	int root,n;
	int Son(int p){ return(p==V[V[p].fa].son[1]); }
	void Pushup(int p){ V[p].siz=V[lch].siz+V[rch].siz+1; }
	void Dfs(int p){ if(!p)return; V[p].siz=1;Dfs(lch),Dfs(rch),Pushup(p);ans+=V[p].siz; }
	void Init(){
		Rep(i,1,n){
			int x,y;cin>>x>>y;
			V[i].son[0]=x,V[i].son[1]=y;
			if(x)V[x].fa=i;if(y)V[y].fa=i;
		}
		Rep(i,1,n)if(!V[i].fa)root=i;
		Dfs(root);
	}
}L,R;

bool Bl[maxn],Br[maxn];
#define V L.V
void RotateL(int p){
	int f=V[p].fa,s=L.Son(p),lf=V[f].fa,ls=L.Son(f);
	ans-=V[p].siz+V[f].siz;
	if(s){
		V[f].son[1]=V[p].son[0];
		if(V[p].son[0])V[V[p].son[0]].fa=f;
		V[p].son[0]=f,V[f].fa=p,V[p].fa=lf;
		if(Bl[f]){
			int num=V[p].siz;
			int ax=V[V[p].son[1]].siz,ay=V[f].siz,bx=B.Find(1,1,n,num);
			ans-=1LL*(num-ax)*B.Siz(1,1,n,num+1,ay)+bx;
			A.Modify(1,1,n,num,-1),Bl[f]=false;
		}
		L.Pushup(f),L.Pushup(p);
	}else{
		V[f].son[0]=V[p].son[1];
		if(V[p].son[1])V[V[p].son[1]].fa=f;
		V[p].son[1]=f,V[f].fa=p,V[p].fa=lf;
		L.Pushup(f),L.Pushup(p);
		if(Bl[f]){
			int num=V[f].siz;
			int ax=V[V[f].son[1]].siz,ay=V[p].siz,bx=B.Find(1,1,n,num);
			ans+=1LL*(num-ax)*B.Siz(1,1,n,num+1,ay)+bx;
			A.Modify(1,1,n,num,1),Bl[p]=true;
		}
	}
	if(lf)V[lf].son[ls]=p;
	if(L.root==f)L.root=p;
	ans+=V[p].siz+V[f].siz;
}
#undef V

#define V R.V
void RotateR(int p){
	int f=V[p].fa,s=R.Son(p),lf=V[f].fa,ls=R.Son(f);
	ans-=V[p].siz+V[f].siz;
	if(s){
		V[f].son[1]=V[p].son[0];
		if(V[p].son[0])V[V[p].son[0]].fa=f;
		V[p].son[0]=f,V[f].fa=p,V[p].fa=lf;
		R.Pushup(f),R.Pushup(p);
		if(Br[f]){
			int num=V[f].siz;
			int ax=V[V[f].son[0]].siz,ay=V[p].siz,bx=A.Find(1,1,n,num-1);
			ans+=1LL*(num-ax)*A.Siz(1,1,n,num,ay-1)+bx;
			B.Modify(1,1,n,num,1),Br[p]=true;
		}
	}else{
		V[f].son[0]=V[p].son[1];
		if(V[p].son[1])V[V[p].son[1]].fa=f;
		V[p].son[1]=f,V[f].fa=p,V[p].fa=lf;
		if(Br[f]){
			int num=V[p].siz;
			int ax=V[V[p].son[0]].siz,ay=V[f].siz,bx=A.Find(1,1,n,num-1);
			ans-=1LL*(num-ax)*A.Siz(1,1,n,num,ay-1)+bx;
			B.Modify(1,1,n,num,-1),Br[f]=false;
		}
		R.Pushup(f),R.Pushup(p);
		
	}
	if(lf)V[lf].son[ls]=p;
	if(R.root==f)R.root=p;
	ans+=V[p].siz+V[f].siz;
}
#undef V


void solve(){
	cin>>L.n>>R.n;n=max(L.n,R.n);
	L.Init(),R.Init();
	for(int p=L.root;p;p=L.V[p].son[1])A.Modify(1,1,n,L.V[p].siz,1),Bl[p]=true;
	for(int p=R.root;p;p=R.V[p].son[0])B.Modify(1,1,n,R.V[p].siz,1),Br[p]=true;
	for(int p=L.root;p;p=L.V[p].son[1])
		ans+=1LL*L.V[p].siz*B.Siz(1,1,n,L.V[p].siz+1,p==L.root ? n : L.V[L.V[p].fa].siz);
	for(int p=R.root;p;p=R.V[p].son[0])
		ans+=1LL*R.V[p].siz*A.Siz(1,1,n,R.V[p].siz,p==R.root ? n : R.V[R.V[p].fa].siz-1);
	cout<<ans<<"\n";
	cin>>q;
	while(q--){
		int opt,x;cin>>opt>>x;
		if(opt==1)RotateL(x);
		else RotateR(x);
		cout<<ans<<"\n";
	}
}

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

C.打扫笛卡尔

套路的设\(f_i\)表示一棵大小为\(i\)的笛卡尔树的期望深度，枚举左右子树大小合并转移，每个点的贡献是\(P(x) \times dep_x\) 的形式，合并的时候深度加一，于是再维护一个\(g_i\)表示概率和，于是就可以转移了。简单化一化柿子发现最后全都合并同类项了，拆开组合数后是一个乘下降幂系数的前缀和，比对下系数发现每次就是再乘个\(i-1\)，于是直接递推就行了。

点击查看代码 
// ubsan: undefined
// accoders
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-ffast-math")
#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=1e7+10;

int n,Mod;
ll f,g[maxn],h[maxn],preg[maxn],preh[maxn];
int fac[maxn],inv[maxn];

void solve(){
	cin>>n>>Mod;
	fac[0]=inv[0]=1;Rep(i,1,n)fac[i]=1LL*fac[i-1]*i%Mod;
	f=1,g[1]=1,h[1]=2%Mod;
	Rep(i,2,n){
		preh[i-1]=1LL*preh[i-1]*(i-1)%Mod;
		preg[i-1]=1LL*preg[i-1]*(i-1)%Mod;
		f=(fac[i]+preh[i-1]+h[i-1])%Mod;
		g[i]=(fac[i]+preg[i-1]+g[i-1])%Mod;
		h[i]=(f+g[i])%Mod;
		preh[i]=(preh[i-1]+h[i-1])%Mod;
		preg[i]=(preg[i-1]+g[i-1])%Mod;
		/*Rep(j,1,i-1)
			f[i]=(f[i]+1LL*(f[j]+g[j])%Mod*inv[j]%Mod*fac[i-1]%Mod)%Mod,
			g[i]=(g[i]+1LL*g[j]*inv[j]%Mod*fac[i-1]%Mod)%Mod;
		f[i]=(f[i]+fac[i])%Mod;
		g[i]=(g[i]+fac[i])%Mod;*/
	//	cerr<<f[i]<<" "<<g[i]<<"\n";
	}
	cout<<f<<"\n";
}

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

标签：27,fa,省选,siz,son,int,联测,define,Mod
From： https://www.cnblogs.com/Delov/p/17107668.html

相关文章

  • DNA甲基化芯片分析01: 使用methylumi和limma分析27K DNA甲基化芯片数据
    前言27K的数据是很老的芯片数据，但是客户有需求就要找方法分析，主流的DNA甲基化芯片R包minfi和champ都只支持450K和850K的芯片。所以在bioconductor中搜索到了methylumi这......
  • 省选模拟28
    说句闲话学了会儿头插dp，转移是这样写的，\(Chen\_jr\)锐评：插头你还短路，你不烧谁烧于是脑子烧坏了来补题解(!is_d)&&(!is_r)&&mp[i+1][j]&mp[i][j+1]//needtomake......
  • UE4.27接入安卓SDK
    1.安装AndroidSKD+NDK过程中遇到了报错：Exceptioninthread"main"  java.lang.NoClassDefFoundError:javax/xml/bind/annotation/XmlSchema  网上给的解决方......
  • 剑指offer——Day27 栈与队列（困难）
    Day272023.2.9栈&队列（困难）剑指Offer59-Ⅰ.滑动窗口的最大值自己实现这种滑动窗口的题直接用双指针来做了，做出来了，正确性是对的，但是时间太长了，超出时间限制了，先把......
  • node: /lib64/libm.so.6: version `GLIBC_2.27' not found
    场景cenos7服务器使用nvm安装的node之后，只要使用npm或者node，均会出现以下问题[root@172~]#npm-vnode:/lib64/libm.so.6:version`GLIBC_2.27'notfound(required......
  • 「解题报告」[省选联考 2022] 序列变换
    我不是很能理解？神奇贪心题。括号序列考虑直接整树形结构，然后操作就是将一个子树内所有儿子放到另一颗子树里，并把这个点单独放到这个子树内，贡献为\(x\)乘终点子树权值加......
  • 【CCCC】L2-027 名人堂与代金券 (25分)，模拟水题
    problemL2-027名人堂与代金券(25分)对于在中国大学MOOC（http://www.icourse163.org/）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到60分及以上，并且......
  • Spring27 - 基于注解的事务管理
    没有事务时遇到的问题模拟场景用户购买图书，先查询图书的价格，再更新图书的库存和用户的余额假设用户id为1的用户，购买id为1的图书用户余额为50，而图书价格为80购买图书之......
  • CF #727（div2）B. Love Song，前缀和
    problemB.LoveSongtimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputPetyaoncewroteasadlovesonga......
  • CF #727（div2）D. PriceFixed， 贪心，双指针
    problemD.PriceFixedtimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputLenaisthemosteconomicalgirli......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99