【MX-X1-T6】「KDOI-05」简单的图上问题

huazai676 · 2024-09-27 19:46:44 · 题解

【MX-X1-T6】「KDOI-05」简单的图上问题

直接计算连通块数量难度较大，由平面图性质利用欧拉公式 V-E+F=C（F 为有界面数量）转换成计算点数、边数、面数。如果一个点被 t 个环包围，那么仅在 t\choose z 种情况下这个点出现在 z 个环的交集中，所以它对答案的贡献为 t\choose z。边、面的情况同理。所以只需要对于每个点、边、面统计有多少个环包含它。

与 std 不同，这里用同一种方法统计点、边、面的贡献。

对于统计每个面的贡献，建出平面图的对偶图，再以无界面的点为根随便建一颗生成树。脑补一下图：一棵树树枝插进一个环里。如何快速给环覆盖上的每个节点都加 1 呢？当树枝进入环时，即节点 u 在环内，fa_u 在环外时，给 u 子树节点都加 1；在树枝出环时，即 fa_u 在环内，u 在环外时，给 u 子树减 1。

如何统计点和边的贡献？回到原图，如果一个面被环包含，那么所有面上的点也被环包含。所以可以再最后把每个面的贡献加到点上，这样每个点 u 都会被统计 d_u（d_u 为点 u 的度数，也是与 u 相邻的面的个数）次，最后再除掉；但是还没结束，那些恰好在环上的点冰不会被统计恰好 d_u 次，因为每次只有环内的面的贡献加到了这些点上。但注意到这些点加起来也不会超过 10^5 个，于是处理环时对于每个环上点把贡献补成 d_u 就好了（加上环外相邻面的数量），这样最后除掉就是对的。边同理。

不用平衡树自然是最优解。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#define PII pair<int,int>
#define x first
#define y second

typedef long long ll;

using namespace std;

PII operator-(const PII& u,const PII& v)
{
    return {u.x-v.x,u.y-v.y};
}

ll operator*(const PII& u,const PII& v)
{
    return 1LL*u.x*v.y-1LL*u.y*v.x;
}

int qt(const PII& u)
{
    if(u.x>0&&u.y>=0) return 1;
    if(u.y>0&&u.x<=0) return 2;
    if(u.x<0&&u.y<=0) return 3;
    if(u.y<0&&u.x>=0) return 4;
    return 0;
}

bool operator<(const PII& u,const PII& v)
{
    int i=qt(u),j=qt(v);
    return i==j? u*v>0:i<j;
}

const int N=1e5+10,M=N*6,mod=998244353;

int n,m,k,cnt,idx;
PII p[N];
struct edge
{
    int from,to,id,val;
}eg[M<<1];
vector<edge> G[N];
void add_edge(int u,int v)
{
    eg[cnt]={u,v,cnt,0};
    G[u].push_back(eg[cnt]);
    cnt++;
}
bool operator<(const edge& u,const edge& v)
{
    return p[u.to]-p[u.from]<p[v.to]-p[v.from];
}

int root,fa[M];
ll tag[M][3];
vector<int> T[M];
bool vis[M];

void dfs(int u)
{
    vis[u]=true;
    for(int v:T[u])
    {
        if(vis[v]) continue;
        fa[v]=u;
        tag[v][2]+=tag[u][2];
        dfs(v);
    }
}

int st[N],tp;
int stk[M],top;
bool ins[M];

ll ksm(ll x,ll y)
{
    ll res=1;
    while(y)
    {
        if(y&1) res=res*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return res;
}
ll fac[N],inv[N];

ll C(int x,int y)
{
    if(x<y) return 0;
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}

int main()
{
    fac[0]=1;
    for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
    inv[N-1]=ksm(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add_edge(u,v),add_edge(v,u);
    }
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());

    for(int i=0;i<cnt;i++)
    {
        if(eg[i].val) continue;
        int now=i;
        idx++;
        ll s=0;
        do
        {
            s+=p[eg[now].from]*p[eg[now].to];
            eg[now].val=idx;
            int u=eg[now].to;
            auto it=lower_bound(G[u].begin(),G[u].end(),eg[now^1]);
            if(it==G[u].begin()) it=G[u].end();
            it--;
            now=it->id;
        }while(now!=i);
        if(s<0) root=idx;
    }
    for(int i=0;i<cnt;i++)
    {
        int u=eg[i].val,v=eg[i^1].val;
        T[u].push_back(v);
    }
    dfs(root);

    for(int o=1;o<=k;o++)
    {
        cin>>tp;
        for(int i=0;i<tp;i++) cin>>st[i];
        ll s=0;
        for(int i=0;i<tp;i++) s+=p[st[i]]*p[st[(i+1)%tp]];
        if(s<0) reverse(st,st+tp);
        for(int i=0;i<tp;i++)
        {
            int u=st[i],v=st[(i+1)%tp];
            auto it=lower_bound(G[u].begin(),G[u].end(),(edge){u,v,0,0});
            int in=eg[it->id].val,out=eg[it->id^1].val;
            tag[it->id^1][1]++;
            if(!ins[in]&&fa[in]==out) tag[in][2]++,ins[stk[++top]=in]=true;
            else if(!ins[out]&&fa[out]==in) tag[out][2]--,ins[stk[++top]=out]=true;
        }
        while(top) ins[stk[top--]]=false;
        for(int i=0;i<tp;i++)
        {
            int l=st[(i-1+tp)%tp],mid=st[i],r=st[(i+1)%tp];
            auto it1=lower_bound(G[mid].begin(),G[mid].end(),(edge){mid,l,0,0}),
                 it2=lower_bound(G[mid].begin(),G[mid].end(),(edge){mid,r,0,0});
            int tot=G[mid].size();
            tag[mid][0]+=(it2-it1+tot)%tot;
        }
    }
    memset(vis,0,sizeof vis);
    dfs(root);
    for(int i=0;i<cnt;i++)
    {
        int u=eg[i].from,in=eg[i].val;
        tag[u][0]+=tag[in][2];
        tag[i][1]+=tag[in][2];
    }
    for(int i=1;i<=n;i++) tag[i][0]/=G[i].size();

    int q;
    cin>>q;
    while(q--)
    {
        int z;
        cin>>z;
        ll ans=0;
        for(int i=1;i<=n;i++) ans=(ans+C(tag[i][0],z))%mod;
        for(int i=0;i<cnt;i+=2) ans=(ans-C(tag[i][1],z))%mod;
        for(int i=1;i<=idx;i++) ans=(ans+C(tag[i][2],z))%mod;
        cout<<(ans+mod)%mod<<'\n';
    }

    return 0;
}