Loj #3056. 「HNOI2019」多边形
小 R 与小 W 在玩游戏。
他们有一个边数为 (n) 的凸多边形，其顶点沿逆时针方向标号依次为 (1,2,3, ldots , n)。最开始凸多边形中有 (n) 条线段，即多边形的 (n) 条边。这里我们用一个有序数对 ((a, b))（其中 (a < b)）来表示一条端点分别为顶点 (a, b) 的线段。
在游戏开始之前，小 W 会进行一些操作。每次操作时，他会选中多边形的两个互异顶点，给它们之间连一条线段，并且所连的线段不会与已存的线段重合、相交（只拥有一个公共端点不算作相交）。他会不断重复这个过程，直到无法继续连线，这样得到了状态 (S_0)。(S_0) 包含的线段为凸多边形的边与小 W 连上的线段，容易发现这些线段将多边形划分为一个个三角形区域。对于其中任意一个三角形，其三个顶点为 (i,j,k(i < j < k))，我们可以给这个三角形一个标号 (j)，这样一来每个三角形都被标上了 (2,3, ldots , n − 1) 中的一个，且没有标号相同的两个三角形。
小 W 定义了一种「旋转」操作：对于当前状态，选定 (4) 个顶点 (a,b,c,d)，使其满足 (1 ≤ a < b < c <d ≤ n) 且它们两两之间共有 (5) 条线段——((a,b), (b,c), (c,d), (a,d), (a,c))，然后删去线段 ((a,c))，并连上线段 ((b,d))。那么用有序数对 ((a, c)) 即可唯一表示该次「旋转」。我们称这次旋转为 ((a,c)) 「旋转」。显然每次进行完“旋转”操作后多边形中依然不存在相交的线段。
当小 W 将一个状态作为游戏初始状态展示给小 R 后，游戏开始。游戏过程中，小 R 每次可以对当前的状态进行「旋转」。在进行有限次「旋转」之后，小 R 一定会得到一个状态，此时无法继续进行「旋转」操作，游戏结束。那么将每一次「旋转」所对应的有序数对按操作顺序写下，得到的序列即为该轮游戏的操作方案。
为了加大难度，小 W 以 (S_0) 为基础，产生了 (m) 个新状态。其中第 (i) 个状态 (S_i) 为对 (S_0) 进行一次「旋转」操作后得到的状态。你需要帮助小 R 求出分别以 (S_0, S_1, ldots , S_m) 作为游戏初始状态时，小 R 完成游戏所用的最少「旋转」次数，并根据小 W 的心情，有时还需求出旋转次数最少的不同操作方案数。由于方案数可能很大，输出时请对 (10^9+7) 取模。
输入格式
第一行一个整数 (W)，表示小 W 的心情。若 (W) 为 (0) 则只需求出最少的「旋转」次数，若 (W) 为 (1) 则还需求出「旋转」次数最少时的不同操作方案数。
第二行一个正整数 (n)，表示凸多边形的边数。
接下来 (n - 3) 行，每行两个正整数 (x, y)，表示小 W 在 (S_0) 中连的一条线段，端点分别为 (x, y)。保证该线段不与已存的线段重合或相交。
接下来一行一个整数 (m)，表示小 W 以 (S_0) 为基础产生的新状态个数。
接下来 (m) 行，每行两个整数。假设其中第 (i) 行为 (a, b)，表示对 (S_0) 进行 ((a, b))「旋转」后得到 (S_i)。
输出格式
输出共 (m + 1) 行。
若 (W) 为 (0) 则每一行输出一个整数，第 (i(i = 1,2, ldots , m, m + 1)) 行输出的整数表示 (S_{i−1}) 作为初始局面的最少「旋转」次数。
若 (W) 为 (1) 则每一行输出两个整数，第 (i(i = 1,2, ldots , m, m + 1)) 行输出的两个整数依次表示 (S_{i−1}) 作为初始局面的最少「旋转」次数、「旋转」次数最少的不同操作方案数对 (10^9+7) 取模的结果。
数据范围与提示
对于所有输入数据，保证：(3le nle 10^5,0le mle 10^5)。
(\)
分析一下观察样例可以发现最终的状态一定是所有边与(n)相连。
我们假设初始状态下没有与(n)相连的边有(k)条，那么第一问的答案就是(k)。如果一条没有与(n)相连的边的两个端点都与(n)相连，那么我们就可以「旋转」这条边，使其与(n)相连。
初始状态下，有些边可能需要「旋转」但「旋转」后不与(n)相连。这是因为它被“挡住”了（观察样例的图感受一下）。我们只有「旋转」了“遮挡”(i)的所有边后才能「旋转」(i)。因为这是个平面图，所以我们根据"遮挡"关系可以建出一个森林。于是第二问就可以(O(n))求解。
考虑题目中的(m)次操作。如果「旋转」后的边不与(n)相连，则第一问答案不变，否则(-1)。对于第二问，我们发现「旋转」第(i)个点后就是将(i)的一个儿子与(i)的兄弟（前提是(i)有父亲）交换。更进一步会发现这是个二叉森林，所以找到交换的儿子也比较容易。因为树形态变化不会很大，所以第二问维护也不太难。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
const ll mod=1e9+7;
ll ksm(ll t,ll x) {
ll ans=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1) ans=ans*t%mod;
return ans;
}
int W;
int n,m;
map<int,int>id[N];
bool tag[N];
struct edge {
int l,r;
bool operator <(const edge &a)const {
if(l!=a.l) return l<a.l;
return r>a.r;
}
}s[N];
vector<int>q;
bool cmp(int a,int b) {return s[a]<s[b];}
int tot;
int st[N],top;
int fa[N];
struct road {int to,nxt;}e[N];
int h[N],cnt;
void add(int i,int j) {e[++cnt]=(road) {j,h[i]};h[i]=cnt;}
ll fac[N],ifac[N];
ll C(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int size[N];
ll f[N];
void dfs1(int v) {
f[v]=1;
for(int i=h[v];i;i=e[i].nxt) {
int to=e[i].to;
dfs1(to);
size[v]+=size[to];
f[v]=f[v]*f[to]%mod*C(size[v],size[to])%mod;
}
size[v]++;
}
ll up[N];
ll imul[N],fmul[N];
int sn[N];
void dfs2(int v) {
ll ans=up[v]*f[v]%mod;
for(int i=h[v];i;i=e[i].nxt) {
int to=e[i].to;
up[to]=ans*ksm(f[to]%mod,mod-2)%mod;
dfs2(to);
}
}
int main() {
W=Get();
n=Get();
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=ksm(fac[n],mod-2);
for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
int a,b;
for(int i=1;i<=n-3;i++) {
a=Get(),b=Get();
if(a>b) swap(a,b);
id[a][b]=++tot;
s[tot].l=a,s[tot].r=b;
}
m=Get();
for(int i=1;i<=n-3;i++)
if(s[i].r!=n) q.push_back(i),tag[i]=1;
sort(q.begin(),q.end(),cmp);
int top=0;
for(int i=0;i<q.size();i++) {
int now=q[i];
while(top&&s[st[top]].r<s[now].r) top--;
if(top) {
fa[now]=st[top];
add(st[top],now);
} else {
add(0,now);
}
st[++top]=now;
}
dfs1(0);
up[0]=1;
dfs2(0);
tag[0]=1;
for(int i=0;i<=n;i++) {
if(!tag[i]) continue ;
fmul[i]=imul[i]=1;
for(int j=h[i];j;j=e[j].nxt) {
imul[i]=imul[i]*ifac[size[e[j].to]]%mod;
fmul[i]=fmul[i]*f[e[j].to]%mod;
}
}
cout<<q.size()<<" ";
if(W) cout<<f[0]<<"
";
else cout<<"
";
int tot=q.size();
f[n+1]=1;
size[n+1]=0;
for(int i=1;i<=n;i++) {
if(tag[i]&&fa[i]) {
int sn1=n+1,sn2=n+1;
for(int j=h[i];j;j=e[j].nxt) {
int to=e[j].to;
if(s[to].l==s[i].l) sn1=to;
if(s[to].r==s[i].r) sn2=to;
}
if(s[fa[i]].l==s[i].l) sn[i]=sn1;
else sn[i]=sn2;
}
}
while(m--) {
a=Get(),b=Get();
if(a>b) swap(a,b);
int now=id[a][b];
if(fa[now]==0) {
cout<<tot-1<<" ";
ll ans=fmul[now]*fmul[0]%mod*ksm(f[now],mod-2)%mod;
ans=ans*fac[tot-1]%mod*imul[now]%mod*imul[0]%mod*fac[size[now]]%mod;
if(W) cout<<ans<<"
";
else cout<<"
";
} else {
cout<<tot<<" ";
int alter=n+1;
for(int i=h[fa[now]];i;i=e[i].nxt) if(e[i].to!=now) alter=e[i].to;
ll f_now=f[now];
f_now=f_now*ksm(C(size[now]-1,size[sn[now]])*f[sn[now]]%mod,mod-2)%mod;
f_now=f_now*f[alter]%mod*C(size[now]-1-size[sn[now]]+size[alter],size[alter])%mod;
ll ans=f_now*f[sn[now]]%mod;
ans=ans*C(size[fa[now]]-1,size[sn[now]])%mod;
if(W) cout<<ans*up[fa[now]]%mod<<"
";
else cout<<"
";
}
}
return 0;
}