怎么没有中文题解啊，写一篇好了

[USACO21FEB] Counting Graphs P

Declarations

定义 $d$ 为到某个点的最短路，$d'$ 为到某个点，奇偶性与 $d$ 不同的最短路。显然 $n$ 个数对 $(d,d')$ 确定了所有 $f_G(u,k)$ 的值。

用 $S(a,b)$ 表示 $d=a,d'=b$ 的点的集合。

将边分为三类：

• 一类，$(d-1,d'-1)\to (d,d')$
• 二类，$(d+1,d'-1)\to (d,d')$
• 三类，$(d,d+1)\to (d,d+1)$

注意到所有边一定属于三类之一。

设 $f(a,b,x)$ 表示已经 dp 到了 $(a,b)$，已经确定了所有 $a'+b'<a+b$ 或 $a'+b'=a+b$ 且 $a'<a$ 的点间连边情况，此时 $(a,b)$ 中还留下了 $x$ 个接口（即需要后面的往回连上的点数），的方案数。

设 $g(a,b,x)$ 定义同上，只是在 $g$ 上，我们目前只确定了二类边，并且 $S(a,b)$ 中恰有 $x$ 个点没有得到二类边的方案数。

Calculating g()

$$g(a,b,x)=\binom {|S(a,b)|}x \sum_{y=0}^{|S(a-1,b+1)|} f(a-1,b+1,y) F(|S(a-1,b+1)|,y,|S(a,b)|-x)$$

其中 $F(U,x,y)$ 表示在一个大小为 $U$ 的集合和一个大小为 $y$ 的集合之间连边，使得前一个集合中 $1\sim x$，后一个集合中所有点的度数都至少为 $1$ 的方案数。可以容斥计算 $F$：

$$F(U,x,y)=\sum_{i=0}^x(-1)^i\binom xi(2^{U-i}-1)^y$$

Calculating f()

$$f(a,b,x)=\sum_{y=0}^{|S(a,b)|} \binom {|S(a,b)|-y}{x}g(a,b,y) (2^{|S(a-1,b-1)|}-1)^{|S(a,b)|-x}$$

Calculating the answer

我们只需求每一个连续段的结果之积。

若某层最后一个节点形如 $(d,d+1)$，最后留出 $k$ 个接口等价于要在这 $k$ 个点之间连边，使得每个点的度数都至少为 $1$。这个方案数可以容斥算（注意可以连自环）：

$$G(k)=\sum_{i=0}^k (-1)^i\binom ki2^{\frac {(|S(d,d+1)|-i)(|S(d,d+1)|-i+1)}2}$$

这时总答案等于

$$\sum_{i=0}^{|S(d,d+1)|} f(d,d+1,i)G(i)$$

否则最后一个节点就不能有接口，直接乘上 $f(a,b,0)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int dis[205],n,m,ans,f[205][205][105],g[205][205][105],C[205][205],pw2[205][205],pw[40005],sum[205];
vector<int> G[205];
struct Pair{
	int x,y;
}a[205];
int Power(int x,int y){
	int ret=1;
	while(y) {
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
const bool operator <(const Pair x,const Pair y){
	if(x.x+x.y!=y.x+y.y)return x.x+x.y<y.x+y.y;
	return x.x<y.x;
}
const bool operator ==(const Pair x,const Pair y){
	return !(x<y)&&!(y<x);
}
void upd(int &x,int y){
	x=(x+y)%mod;
}
int F(int U,int x,int y){
	int ret=0;
	for(int i=0,f=1;i<=x;i++,f=mod-f)upd(ret,1ll*f*C[x][i]%mod*pw2[U-i][y]%mod);
	return ret;
}
void Solve(){
	scanf("%d%d",&n,&m),ans=1;
	for(int i=0;i<=2*n;i++)dis[i]=0x3f3f3f3f,G[i].clear();
	for(int i=0;i<=2*n;i++)for(int j=0;j<=2*n;j++)for(int k=0;k<=n;k++)f[i][j][k]=g[i][j][k]=0;
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v+n),G[v+n].push_back(u),G[u+n].push_back(v),G[v].push_back(u+n);
	}
	queue<int> q;
	q.push(1),dis[1]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int y:G[x])if(dis[y]>dis[x]+1)dis[y]=dis[x]+1,q.push(y);
	}
	if(dis[1+n]==0x3f3f3f3f){
		for(int i=0;i<=n;i++)sum[i]=0;
		for(int i=1;i<=n;i++)sum[min(dis[i],dis[i+n])]++;
		for(int i=1;i<=n;i++)ans=1ll*ans*Power(Power(2,sum[i-1])-1,sum[i])%mod;
		return cout<<ans<<'\n',void();
	}
	for(int i=1;i<=n;i++)a[i]={min(dis[i],dis[i+n]),max(dis[i],dis[i+n])};
	sort(a+1,a+n+1);
	map<Pair,int> s;
	for(int i=1;i<=n;i++){
		int j=i-1;
		while(a[j+1]==a[i]&&j<n)j++;
		s[a[i]]=j-i+1;
		int p=a[i].x,q=a[i].y,S=j-i+1,T=s[{p-1,q+1}],O=s[{p-1,q-1}];
		if(!T)g[p][q][(i==1?0:S)]=1;
		else {
			for(int x=0;x<=S;x++)
				for(int y=0;y<=T;y++)
					upd(g[p][q][x],1ll*f[p-1][q+1][y]*F(T,y,S-x)%mod*C[S][x]%mod);
		}
		for(int x=0;x<=S;x++){
			for(int y=0;x+y<=S;y++)
				upd(f[p][q][x],1ll*C[S-y][x]*g[p][q][y]%mod*pw2[O][S-x]%mod);
		}
		if(j==n||a[j+1].x!=p+1||a[j+1].y!=q-1){
			if(p+1!=q)ans=1ll*ans*f[p][q][0]%mod;
			else {
				int tmp=0;
				for(int i=0;i<=S;i++)
					for(int j=0,o=1;j<=i;j++,o=mod-o)
						upd(tmp,1ll*o*C[i][j]%mod*pw[(S-j)*(S-j+1)/2]%mod*f[p][q][i]%mod);
				ans=1ll*ans*tmp%mod;
			}
		}
		i=j;
	}
	cout<<ans<<'\n';
}
int main(){
	for(int i=0;i<=200;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		for(int j=0;j<=200;j++)pw2[i][j]=Power(Power(2,i)-1,j);
	}
	for(int i=0;i<=40000;i++)pw[i]=Power(2,i);
	int t;
	scanf("%d",&t);
	while(t--)Solve();
	return 0;
}