前言

这是一道非常妙妙的题，每一个档对应一个做法，且每个做法都需要有一定的计数知识和优化技巧。

简要题意

给你一张 $n$ 个点、$m$ 条边的图，要求相邻两点颜色不同，$z$ 次询问，每次询问你使用 $k$ 种颜色对图染色的方案数对 $10^9+7$ 取模。

每一档的数据范围及性质见题面。

解法

Subtask 1

其数据范围完全包含于下一个子任务，不进行另外的算法设计。

Subtask 2

个人感觉难度：下位紫。

这时 $n$ 非常小，我们考虑状压 dp，设 $f_{i,S}$ 表示使用前 $i$ 种颜色为点集 $S$ 染上颜色，且每种颜色都要用到的方案数，转移是简单的，直接枚举真子集并判断补集是否合法即可，但关键是我们需要使用平方的时间复杂度来判断一个新加入的颜色相同的点的集合是否满足条件（即是否存在两点相邻），这样的话时间复杂度是 $O(3^n\cdot n^3)$ 的，无法通过。

考虑到我们会多次重复判断一个集合合不合法，且合不合法与具体颜色无关，于是我们对于每一种点集都预处理其合不合法，查询的话就是枚举要用多少种颜色，用个组合数乘一下就行了，这样复杂度就是 $O(3^n\cdot n)$ 的，可以通过。

Subtask 3

个人感觉难度：中位紫。

这时 $m$ 较小，但对边集进行状压 dp 似乎又不太好做。这时我们可以进行容斥，这里的容斥的意思是，我们枚举一个边的集合代表这个集合内的边所连接的两个点必须同色，其余的不作限制，这样单种情况染色的方案数就是 $k^T$，其中 $k$ 为颜色数目；$T$ 为这些边的限制所形成的连通块个数，用并查集维护即可。所以你只需要在每次询问时都对这 $2^m$ 种情况容斥一遍就行了，时间复杂度为 $O(2^m\cdot zm\log n)$，炸飞了。

考虑到连通块个数的上界是 $n$，也即容斥的每一项的次数最大为 $n$，于是可以预处理出每一个次数对应的容斥的系数（类似于将上一段中的方法合并了同类项），询问时直接扫一遍所有次数，边累加答案时边对于次幂进行累乘（去掉了快速幂的 $\log$），这样总复杂度为 $O(2^m\cdot m\log n+zn)$，还是无法通过。

考虑优化预处理复杂度，并不套路地，我们使用深搜来慢慢加入边的限制，每一步都从上一步选择的边的后一条边开始枚举并继续递归，能做到不重不漏。至于连通块个数，考虑使用可撤销并查集来维护，在回溯时撤销，并在开始递归时统计每个次数对应的系数。这样的话时间复杂度是 $O(2^m\log n+zn)$，可以通过。

Subtask 4

个人感觉难度：中位蓝。

大概画一下你就知道，这种情况指的是图是由很多个单独的环组成的。首先有个经典结论是不同的环长只有根号级别个，且我们知道对于每一个环长的答案是一样的，于是考虑先用并查集找出有哪些环长，再在询问时分不同的环长处理。

现在我们面临的就是典型的小奥题。设 $f_i$ 表示环长为 $i$ 时的染色方案数，如果我们此时不考虑首尾颜色是否相同，那么答案就是 $k(k-1)^{i-1}$，其中 $k$ 为颜色数。然后我们再将首尾颜色相同的方案减掉，那这个方案怎么算呢？我们发现这个时候有个要求，那就是倒数第二个位置的颜色要和最后一个位置的颜色不同，也即倒数第二个位置的颜色与第一个位置颜色不同，发现这个限制又形成了一个环，也就是说首尾相同的方案数为 $f_{i-1}$。

整理一下上文可得：$f_i=k(k-1)^{i-1}-f_{i-1}$。如果你对于每次询问的每一种环长都这样递推一下，并且将幂累乘一下，是可以做到 $O(zn)$ 的，可以通过，但是我们还可以更优秀。

我们考虑使用高中数学中求数列通项公式的方法，不管你用什么方法，最终都能得出 $f_i=(k-1)^i+(-1)^i\cdot(k-1)$ 这一结果。用这个公式，你便能做到 $O(z\sqrt{n}\log n)$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=1e9+7;
bool f[20][20];
int dp[20][100010];
int quick_pow(int x,int y){
	int res=1;
	while(y){
		if(y&1)(res*=x)%=Mod;
		(x*=x)%=Mod;
		y>>=1;
	}
	return res;
}
int C(int n,int m){
	int sum=1;
	for(int i=n-m+1;i<=n;i++)(sum*=i)%=Mod;
	for(int i=1;i<=m;i++)(sum*=quick_pow(i,Mod-2))%=Mod;
	return sum;
}
bool yuchuli[100010];
struct node{
	int x,y;
}bian[30];
int fa[100010],sz[100010];
int find(int x){
	if(fa[x]==x)return x;
	return find(fa[x]);
}
int xi[100010];
int n,m,z;
vector<pair<int,pair<int,pair<int,int> > > >st;
void dfs(int S,int ge,int xuan,int start){
	if(xuan%2==0)xi[ge]++;
	else xi[ge]--;
	if(S==(1<<m)-1)return;
	for(int i=start;i<=m;i++){
		int fx=find(bian[i].x),fy=find(bian[i].y);
		bool ff=0;
		if(fx!=fy){
			ff=1;
			if(sz[fx]<sz[fy]){
				st.push_back({fx,{fy,{fa[fx],sz[fx]}}});
				fa[fx]=fy;
				sz[fy]+=sz[fx];
			}
			else{
				st.push_back({fy,{fx,{fa[fy],sz[fy]}}});
				fa[fy]=fx;
				sz[fx]+=sz[fy];
			}
		}
		dfs(S+(1<<(i-1)),ge-ff,xuan+1,i+1);
		if(ff){
			auto pp=st.back();
			st.pop_back();
			fa[pp.first]=pp.second.second.first;
			sz[pp.second.first]-=pp.second.second.second;
		}
	}
}
int Cnt[100010];

signed main(){
	cin>>n>>m>>z;
	if(n<=15){
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			f[x][y]=f[y][x]=1;
		}
		int N=(1<<n)-1;
		for(int i=1;i<=N;i++){
			bool F=1;
			for(int a=0;a<n;a++){
				if(!((1<<a)&i))continue;
				for(int b=a+1;b<n;b++){
					if(!((1<<b)&i))continue;
					if(f[a+1][b+1]){
						F=0;break;
					}
				}
				if(!F)break;
			}
			yuchuli[i]=F;
		}
		dp[0][0]=1;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=N;j++){
				for(int k=j;;k=((k-1)&j)){
					if(k==j)continue;
					if(!dp[i-1][k]){
						if(k==0)break;
						continue;
					}
					if(yuchuli[k^j])(dp[i][j]+=dp[i-1][k])%=Mod;
					if(k==0)break;
				}
			}
		}
		while(z--){
			int k;
			cin>>k;
			int sum=0;
			for(int i=1;i<=min(k,n);i++){
				(sum+=C(k,i)*dp[i][N]%Mod)%=Mod;
			}
			cout<<sum<<"\n";
		}
		return 0;
	}
	if(m<=24){
		for(int i=1;i<=m;i++){
			cin>>bian[i].x>>bian[i].y;
		}
		for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
		dfs(0,n,0,1);
		while(z--){
			int k;
			cin>>k;
			int sum=0,poww=1;
			for(int i=1;i<=n;i++){
				(poww*=k)%=Mod;
				(sum+=xi[i]*poww%Mod)%=Mod;
			}
			cout<<(sum+Mod)%Mod<<"\n";
		}
		return 0;
	}
	for(int i=1;i<=n;i++){
		fa[i]=i,sz[i]=1;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		int fx=find(x),fy=find(y);
		if(fx==fy)continue;
		if(sz[fx]<sz[fy]){
			fa[fx]=fy,sz[fy]+=sz[fx];
		}
		else fa[fy]=fx,sz[fx]+=sz[fy];
	}
	for(int i=1;i<=n;i++){
		if(find(i)==i){
			Cnt[sz[i]]++;
		}
	}
	vector<int>you;
	for(int i=1;i<=n;i++)if(Cnt[i])you.push_back(i);
	while(z--){
		int k;
		cin>>k;
		int sum=1;
		for(int i:you){
			int num=quick_pow(k-1,i);
			if(i%2==0)(num+=k-1)%=Mod;
			else (num-=k-1)%=Mod;
			(sum*=quick_pow(num,Cnt[i]))%=Mod;
		}
		cout<<(sum+Mod)%Mod<<"\n";
	}
	return 0;
}