题解

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9+7;

using ll = long long;

#define f first
#define s second

struct mi {
 	int v; 
 	explicit operator int() const { return v; } 
	mi() { v = 0; }
	mi(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
};
mi& operator+=(mi& a, mi b) { 
	if ((a.v += b.v) >= MOD) a.v -= MOD; 
	return a; }
mi& operator-=(mi& a, mi b) { 
	if ((a.v -= b.v) < 0) a.v += MOD; 
	return a; }
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
mi& operator*=(mi& a, mi b) { return a = a*b; }
mi pow(mi a, ll p) { assert(p >= 0); // asserts are important! 
	return p==0?1:pow(a*a,p/2)*(p&1?a:1); }

using vi = vector<int>;
using vmi = vector<mi>;

int N,M;
vector<vi> adj;
 
vector<array<int,2>> gen_dist() { // BFS
	vector<array<int,2>> dist(N,{MOD,MOD});
	queue<pair<int,int>> q;
	auto ad = [&](int a, int b) {
		if (dist[a][b%2] != MOD) return;
		dist[a][b%2] = b; q.push({a,b});
	};
	ad(0,0);
	while (!q.empty()) {
		pair<int,int> p = q.front(); q.pop();
		for (int t: adj[p.f]) ad(t,p.s+1);
	}
	return dist;
}

mi comb[105][105]; // comb[x][y] = (x choose y)
vmi p2; // stores powers of 2

void solve() {
	cin >> N >> M;
	adj = vector<vi>(N);
	for (int i = 0; i < M; ++i) {
		int a,b; cin >> a >> b; --a,--b;
		adj[a].push_back(b), adj[b].push_back(a);
	}
	vector<array<int,2>> dists = gen_dist();
	for (array<int,2>& t: dists) 
		if (t[0] > t[1]) swap(t[0],t[1]);
	if (dists[0][1] == MOD) { // bipartite
		vi num_at_dist(N);
		for (int i = 0; i < N; ++i) 
			++num_at_dist[min(dists[i][0],dists[i][1])];
		mi ans = 1;
		for (int i = 1; i < N; ++i)
			ans *= pow(p2[num_at_dist[i-1]]-1,num_at_dist[i]);
		cout << (int)ans << "\n";
		return;
	}
	vector<vi> S(4*N,vi(4*N));
	for (array<int,2> t: dists) ++S[t[0]][t[1]];
	mi ans = 1;
	for (int sum = 1; sum < 4*N; sum += 2) {
		vmi dp(S[0][sum]+1); dp.back() = 1;
		for (int a = 1; a <= sum/2; ++a) { // solve in increasing order of a
			int b = sum-a, num = S[a][b];
			vmi dp_int(num+1);
			{ // deal with s_{a-1,b+1} to s_{a,b}
				int prev_num = S[a-1][b+1];
				for (int x = 0; x <= num; ++x) { // x in s_{a,b} with no edges at all, num-x that receive edges
					for (int y = 0; y <= prev_num; ++y) { // y nodes in s_{a-1,b+1} that need an edge
						mi tot_mul = 0;
						for (int k = 0; k <= y; ++k) { // suppose that k out of y didn't actually get an edge
							mi mul = comb[y][k]*pow(p2[prev_num-k]-1,num-x);
							if (k&1) tot_mul -= mul;
							else tot_mul += mul;
						}
						dp_int[x] += tot_mul*dp[y];
					}
					dp_int[x] *= comb[num][x];
				}
			}
			{ // deal with s_{a-1,b-1} to s_{a,b}
				dp = vmi(num+1);
				int lower_num = S[a-1][b-1];
				for (int x = 0; x <= num; ++x) { // x will not be part of such an edge
					for (int y = 0; x+y <= num; ++y) { // y urgently need an edge, num-y don't
						mi mul = comb[num-y][x]*pow(p2[lower_num]-1,num-x);
						dp[x] += mul*dp_int[y];
					}
				}
			}
		}
		// finally, deal with clique edges
		mi ans_for_layer = 0;
		int num = S[sum/2][sum/2+1];
		for (int y = 0; y <= num; ++y) { // how many ways to complete if y need an edge
			mi tot_mul = 0;
			for (int k = 0; k <= y; ++k) {
				mi mul = comb[y][k]*p2[(num-k)*(num-k+1)/2];
				if (k&1) tot_mul -= mul;
				else tot_mul += mul;
			}
			ans_for_layer += tot_mul*dp[y];
		}
		ans *= ans_for_layer;
	}
	cout << (int)ans << "\n";
}
 
int main() {
	comb[0][0] = 1;
	for (int i = 1; i < 105; ++i) {
		comb[i][0] = 1;
		for (int j = 1; j <= i; ++j) 
			comb[i][j] = comb[i-1][j]+comb[i-1][j-1];
	}
	p2 = {1}; 
	for (int _ = 0; _ < 10000; ++_) 
		p2.push_back(2*p2.back());
	int TC; cin >> TC;
	while (TC--) solve();
}

内存和时间击败花神