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\) 取模的结果。

数据范围与提示

对于所有输入数据，保证：\(3\le n\le 10^5,0\le m\le 10^5\)。

\(\\\)

分析一下观察样例可以发现最终的状态一定是所有边与\(n\)相连。

我们假设初始状态下没有与\(n\)相连的边有\(k\)条，那么第一问的答案就是\(k\)。如果一条没有与\(n\)相连的边的两个端点都与\(n\)相连，那么我们就可以「旋转」这条边，使其与\(n\)相连。

初始状态下，有些边可能需要「旋转」但「旋转」后不与\(n\)相连。这是因为它被“挡住”了（观察样例的图感受一下）。我们只有「旋转」了“遮挡”\(i\)的所有边后才能「旋转」\(i\)。因为这是个平面图，所以我们根据"遮挡"关系可以建出一个森林。于是第二问就可以\(O(n)\)求解。

考虑题目中的\(m\)次操作。如果「旋转」后的边不与\(n\)相连，则第一问答案不变，否则\(-1\)。对于第二问，我们发现「旋转」第\(i\)个点后就是将\(i\)的一个儿子与\(i\)的兄弟（前提是\(i\)有父亲）交换。更进一步会发现这是个二叉森林，所以找到交换的儿子也比较容易。因为树形态变化不会很大，所以第二问维护也不太难。

代码：

#include
    
     #define ll long long#define N 100005using 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
     
      id[N];bool tag[N];struct edge {    int l,r;    bool operator <(const edge &a)const {        if(l!=a.l) return l
      
       a.r;    }}s[N];vector
       
        q;bool cmp(int a,int b) {return s[a]
        
         =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
         
          b) swap(a,b); int now=id[a][b]; if(fa[now]==0) { cout<
          
           <<" "; 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<
           
            <<"\n"; else cout<<"\n"; } else { cout<
            
             <<" "; 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<
             
              <<"\n"; else cout<<"\n"; } } return 0;}