题解

思路

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

与 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 ​ 就好了（加上环外相邻面的数量），这样最后除掉就是对的。边同理。

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

Code

#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;
}