P10230题解

题意

给定

n

个顶点的多边形，

n-3

条对角线形成一个三角剖分（顾名思义

n-3

条对角线将多边形分成了一个个三角形）。有两种操作：
1.删除一条对角线，并添加新的一条（算一次操作）。
2.问此时将所有对角线的一端移到

x

上的最小操作次数和其方案数。

注意三角剖分和操作

2

时不能让当前的对角线有交。

突破点

从

sub2

中受到启发，发现最小操作次数就是端点不在

x

上的对角线条数。

简单证明一下：对于一条对角线

(p,q)

，它存在于两个三角形中，所对的点分别记为

x,r

。我们可以删除

(p,q)

，添加

x,r

使得对角线的一端变为

x

，而我们每次可以选择不被其他对角线包含的一条操作。至于一端在

x

上的对角线，我们不进行操作显然更优。

第一步转化

经过最小操作次数的启发，我们可以发现操作的一般顺序。

我们将所有对角线看作不经过

x

的弧的形式，则：

任意两条弧要么不交要么包含（根据三角剖分的性质）。
每次一定选择一条极大的弧（不被其他弧包含的弧），满足操作中对角线无交。
一条弧至多直接包含两条弧（无用）。

第二步转化

将所有弧看作点，将弧与弧之间的包含关系映射为树上的父子关系（大弧为父亲），就得到了一个二叉树形结构。

结合我们上一步的操作顺序，我们就是每次处理一个父亲节点，然后将它的儿子加入到待处理集合中。这样我们的操作方案数就是一个树上拓扑序数，因为弧与弧之间可能无交，也就是可能有很多棵树形成的森林，操作方案数为森林拓扑序数量。

有个经典结论，森林拓扑序数量为

\frac{n!}{\prod sz_{i}}

。

n

为节点数，

sz_{i}

为以

i

为根的子树大小；而这里

n

为不经过

x

的对角线的数量；对于一个点

p

，

sz_{p}

就是这条弧所包含的小弧数量（包括自己）。

设弧为

(l,r)

，则包含数量就是

(r - l - 1)

，只需计算所有不经过

x

的弧的弧长-1的乘积。

所以我们记录每个点上连接的对角线条数

ind[i]

，最小操作次数就是

n - 3 - ind[x]

，方案数就是不经过

x

的弧的条数除以所有弧的包含总数和。

第三步优化

考虑优化复杂度，用树状数组维护

mul[i]

，表示不经过

i

号点的对角线/弧包含总数和（也就是

\prod sz_{i}

这部分）。维护对角线就是维护对角线所对的两条弧上的点：具体的，添加一条对角线就是进行区间乘，删除对角线就是区间乘以逆元。

区间修单点查利用差分思想转为单点修前缀查，

[l,r]

的区间乘就是

l

上乘，

r+1

上乘逆元。

快速幂算逆元，预处理阶乘，树状数组维护，复杂度

O((n+q)\log n)

。

细节

本题的区间为环形区间，要注意

l,r,1,n

的关系。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int MOD =  1e9 + 7;
const int N = 2e5 + 10;
template<typename TY>
inline void read(TY &s){
	ll x = 0,f = 1;
    char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	s = x * f;
}
int n,q;
int ind[N];
ll qpow(ll a,ll b,ll p){
	ll res = 1;
	while(b){
		if(b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res % p;
}
inline ll inverse(ll x){
	return qpow(x,MOD-2,MOD);
}
inline int dist(int x,int y){
	if(x < y) return y - x;
	else return y - x + n;
}
ll mul[N],fac[N];
inline void modify(int x,ll v){
	for(int i=x;i<=n;i+=lowbit(i)) mul[i] = mul[i] * v % MOD;
}
inline ll query(int x){
	ll res = 1;
	for(int i=x;i;i-=lowbit(i)) res = res * mul[i] % MOD;
	return res;
}
inline void M(int l,int r,ll v){
	if(l > r) return;
	modify(l,v); modify(r+1,inverse(v));
}
inline void change(int x,int y,ll v){
	if(x < y){
		M(x+1,y-1,v);
	}
	else{
		M(x+1,n,v);
		M(1,y-1,v);
	}
}
int main(){
	read(n); read(q);
	int a,b;
	fac[0] = 1; 
	for(int i=1;i<=n;i++){
		fac[i] = fac[i - 1] * i % MOD;
		mul[i] = 1;
	}
	for(int i=1;i<=n-3;i++){
		read(a); read(b);
		ind[a]++; ind[b]++;
		change(a,b,dist(b,a)-1);
		change(b,a,dist(a,b)-1);
	} 
	int c,d,opt;
	while(q--){
		read(opt);
		if(opt == 1){
			read(a); read(b); read(c); read(d);
			ind[a]--; ind[b]--; ind[c]++; ind[d]++;
			change(a,b,inverse(dist(b,a)-1));
			change(b,a,inverse(dist(a,b)-1));
			change(c,d,dist(d,c)-1);
			change(d,c,dist(c,d)-1);
		}
		else{
			read(a);
			cout << (n - 3 - ind[a]) << " " << (fac[n-3-ind[a]]) * inverse(query(a)) % MOD << "\n";
		} 
	}
	return 0;
}

题解：P10230 [COCI 2023/2024 #4] Lepeze

文章操作