自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:06:57，当前版本为作者最后更新于2024-12-12 15:36:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

显然，每一个合法的简单回路必定对应三角剖分中的一个子多边形，如图所示。

观察发现，他是若干个联通的三角形的并。

考虑把相邻的三角形当做点，在相邻三角形之间连边，本质上就是求联通块的个数。

注意到三角剖分一定对应了一棵树（归纳易证），因此就是无聊的树形 DP。

如何求三角剖分？直接枚举所有相邻边即可！

复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10,MOD=1e9+7;
int n,tot,bl[MAXN],ans,dp[MAXN];
vector<int> G[MAXN],T[MAXN];
int dis(int i,int j) {
	if(j>=i) return j-i;
	return j+n-i;	
}
void dfs(int u,int f) {
	dp[u]=1;
	for(auto v:T[u]) {
		if(v==f) continue ;
		dfs(v,u),dp[u]=(dp[u]*(dp[v]+1))%MOD;
	}
	ans=(ans+dp[u])%MOD;
	return ;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	map<pair<int,int>,int> mp;
	ffor(i,1,n) G[i].push_back(i%n+1),G[i%n+1].push_back(i);
	ffor(i,1,n-3) {
		int x,y;
		cin>>x>>y;
		G[x].push_back(y),G[y].push_back(x);
		mp[{x,y}]=mp[{y,x}]=i;
	}
	ffor(i,1,n) {
		sort(G[i].begin(),G[i].end(),[&](int A,int B) {return dis(A,i)<dis(B,i);});
		ffor(j,0,G[i].size()-2) {
			int u=i,v=G[i][j],w=G[i][j+1];
			if(u<=v&&u<=w) {
				++tot;
				int id1=mp[{u,v}],id2=mp[{u,w}],id3=mp[{v,w}];
				if(id1) {
					if(bl[id1]) T[tot].push_back(bl[id1]),T[bl[id1]].push_back(tot);
					else bl[id1]=tot;	
				}
				if(id2) {
					if(bl[id2]) T[tot].push_back(bl[id2]),T[bl[id2]].push_back(tot);
					else bl[id2]=tot;
				}
				if(id3) {
					if(bl[id3]) T[tot].push_back(bl[id3]),T[bl[id3]].push_back(tot);
					else bl[id3]=tot;
				}
			}
		}
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}