#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ll long long int #define mod 1000000007 inline int mul(int a,int b){return (int)((ll)a*b%mod);} inline int pow(int a,int b) { int res=1; while(b>0){ if(b&1) res=mul(res,a); b>>=1; a=mul(a,a); } return res; } inline int inv(int x){return pow(x,mod-2);} inline int _abs(int x){return x>0?x:-x;} int n,m,k,T,ans=1,cnt=0; int fac[100001],invfac[100001]; inline int modn(int x) { if(x<0) return x+n; if(x>=n) return x-n; return x; } inline int C(int a,int b) { return mul(mul(fac[a],invfac[b]),invfac[a-b]); } inline int invC(int a,int b) { return mul(mul(invfac[a],fac[b]),fac[a-b]); } struct edge{ int a,b,d1,d2,in,out; }ed[400000]; int st[100001]; inline bool comp(edge e1,edge e2) { if(e1.a==e2.a) return modn(e1.b-e1.a)<modn(e2.b-e2.a); return e1.a<e2.a; } inline int find(int x,int y) { y=modn(y-x); int l=st[x],r=st[x+1]-1,mid; while(l<r){ mid=(l+r)>>1; if(modn(ed[mid].b-x)<y) l=mid+1; else r=mid; } return l; } void read(void) { scanf("%d%d",&T,&n); k=n+n-6; for(int i=n-4;i>=0;i--){ scanf("%d%d",&ed[i].a,&ed[i].b); ed[i].a%=n; ed[i].b%=n; ed[k-i-1].a=ed[i].b; ed[k-i-1].b=ed[i].a; } for(int i=0;i<n;i++){ ed[k].a=i; ed[k++].b=modn(i+1); ed[k].b=i; ed[k++].a=modn(i+1); } fac[0]=1; for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i); invfac[n]=inv(fac[n]); for(int i=n-1;i>=0;i--) invfac[i]=mul(invfac[i+1],i+1); sort(ed,ed+k,comp); int pos=0; for(int i=0;i<=n;i++){ st[i]=pos; while(pos<k&&ed[pos].a==i) pos++; } int p,q; for(int i=0;i<n;i++) for(int j=st[i]+1;j<st[i+1];j++){ p=ed[j].b; q=ed[j-1].b; if(p>q) swap(p,q); if(p<i&&i<q) ed[find(p,q)].out=ed[find(q,p)].out=i; else ed[find(p,q)].in=ed[find(q,p)].in=i; } return; } void dfs(int id) { if(_abs(ed[id].a-ed[id].b)==1){ ed[id].d1=0; ed[id].d2=1; return; } int p=find(ed[id].a,ed[id].out),q=find(ed[id].b,ed[id].out); int r=find(ed[id].b,ed[id].a); dfs(p); dfs(q); ed[id].d1=ed[r].d1=ed[p].d1+ed[q].d1+1; ed[id].d2=ed[r].d2=mul(mul(ed[p].d2,ed[q].d2),C(ed[id].d1-1,ed[p].d1)); return; } int main(void) { read(); for(int i=st[0]+1;i<st[1];i++){ int t=find(ed[i-1].b,ed[i].b); dfs(t); cnt+=ed[t].d1; ans=mul(ans,mul(C(cnt,ed[t].d1),ed[t].d2)); } if(T==0) printf("%d\n",cnt); else printf("%d %d\n",cnt,ans); int p,q,r,a1,a2,t1,t2,A,B,C; scanf("%d",&m); while(m--){ scanf("%d%d",&p,&q); r=find(p,q); if(ed[r].in==0){ a1=cnt-1; a2=mul(inv(cnt),ed[r].d1); } else{ a1=cnt; A=find(p,ed[r].out); B=find(q,ed[r].out); t1=find(p,ed[r].in); t2=find(q,ed[r].in); if(ed[t1].d1<ed[t2].d1) C=t1; else C=t2; a2=mul(inv(ed[B].d1+ed[C].d1+1),ed[A].d1+ed[B].d1+1); } if(T==0) printf("%d\n",a1); else printf("%d %d\n",a1,mul(ans,a2)); } return 0; }
原文:https://www.cnblogs.com/2005lz/p/13040187.html