[HNOI2019]多边形

Luogu5288

注意：n边形里共有n-3条边

最优步数=不与n相连的边数，关键是方案数．

按照处理顺序可以转化为树形结构即二叉树森林，转移方案数用组合数即可

关键是快速处理修改．

1.最优解减少一步，即删掉某棵二叉树的根，合并它的两个儿子．

2.相当于在splay中把它rotate一下，而且不知道为什么它还一定是左儿子

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<cassert>

#define debug(...) fprintf(stderr,__VA_ARGS__)

#define Debug(x) cout<<#x<<"="<<x<<endl

using namespace std;

typedef long long LL;

typedef pair<int,int> pii;

const int INF=1e9+7;

inline LL read(){

    register LL x=0,f=1;register char c=getchar();

    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}

    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();

    return f*x;

}

const int N=100005;

const int mod=1e9+7;

int size[N],ls[N],rs[N],fa[N],fac[N],ifac[N],inv[N];

int W,n,m,sum,ans=1,Ecnt;

vector <int> E[N];

map <pii,int> M;

inline int add(int x,int y){x+=y;return x>=mod?x-mod:x;}

inline int mul(LL x,int y){x*=y;return x>=mod?x%mod:x;}

inline int cal(int x,int y){return mul(fac[x+y],mul(ifac[x],ifac[y]));}

inline int ical(int x,int y){return mul(ifac[x+y],mul(fac[x],fac[y]));}

inline void dfs(int &x,int l,int r,int pre){

	if(l+1==r) return;

	x=++Ecnt;///

	M[pii(l,r)]=x,fa[x]=pre;

	int mid=*upper_bound(E[r].begin(),E[r].end(),l);

	dfs(ls[x],l,mid,x);

	dfs(rs[x],mid,r,x);

	size[x]=size[ls[x]]+size[rs[x]]+1;

	ans=mul(ans,cal(size[ls[x]],size[rs[x]]));

}

inline void answer(int x,int y){

	if(W==0) printf("%d\n",x);

	else printf("%d %d\n",x,y);

}

int main(){

	W=read(),n=read();

	inv[0]=inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;

	for(int i=2;i<=n;i++) inv[i]=mul(inv[mod%i],mod-mod/i);///

	for(int i=2;i<=n;i++) fac[i]=mul(fac[i-1],i),ifac[i]=mul(ifac[i-1],inv[i]);

	for(int i=1;i<=n-3;i++){

		int x=read(),y=read();

		E[x].push_back(y);E[y].push_back(x);

	}

	for(int i=1;i<n;i++) E[i].push_back(i+1),E[i+1].push_back(i);

	E[1].push_back(n),E[n].push_back(1);

	for(int i=1;i<=n;i++) sort(E[i].begin(),E[i].end());

	for(int i=0;i<(E[n].size()-1);i++){

		int tmp=0;

		dfs(tmp,E[n][i],E[n][i+1],0);

		ans=mul(ans,cal(sum,size[tmp]));

		sum+=size[tmp];

	}

	answer(sum,ans);

	m=read();

	for(int i=1;i<=m;i++){

		int a=read(),b=read(),x=M[pii(a,b)];

		int qans=ans,qsum=sum;//-(a==n||b==n);

		if(!fa[x]){

			//assert(qsum==sum-1);

			qsum--;

			qans=mul(qans,ical(size[ls[x]],size[rs[x]]));

			qans=mul(qans,ical(sum-size[x],size[x]));

			qans=mul(qans,cal(sum-size[x],size[ls[x]]));

			qans=mul(qans,cal(sum-size[x]+size[ls[x]],size[rs[x]]));

		}

		else{

			int y=fa[x],k=(rs[y]==x);

			qans=mul(qans,ical(size[ls[x]],size[rs[x]]));

			qans=mul(qans,ical(size[ls[y]],size[rs[y]]));

			if(k==0){

				qans=mul(qans,cal(size[rs[x]],size[rs[y]]));

				qans=mul(qans,cal(size[ls[x]],size[rs[x]]+size[rs[y]]+1));

			}

			if(k==1){

				assert(false);

				qans=mul(qans,cal(size[ls[y]],size[ls[x]]));

				qans=mul(qans,cal(size[rs[x]],size[ls[y]]+size[ls[x]]+1));

			}

		}

		answer(qsum,qans);

	}

}

巴特西

[HNOI2019]多边形

最新文章

热门文章