题目链接
简化题意：有一个 \(n\) 个点的图，问有多少个长度为 \(M\) 的边序列，满足连边后图是二分图。
\(n\le 30,m\le 10^9\)
考虑先强制要求无重边。
定义 \(f_{i,j}\) 为 \(i\) 个点，\(j\) 条边的图的二分图染色数量（染色方式不同算多次）。这个是可以通过枚举黑色点的数量算出来。
然后定义 \(g_{i,j}\) 为 \(i\) 个点，\(j\) 条边的连通图的二分图染色数量。\(g_{i,j}\) 等于 \(f_{i,j}\) 减去不连通的数量，枚举 \(1\) 号点的连通块大小 \(k\) 和边数 \(a\)，然后 \(g_{i,j}\) 减去 \(g_{k,a}\times f_{i-k,j-a}\times \binom{i-1}{k-1}\).
\(g_{i,j}\) 除以2就是 \(i\) 个点，\(j\) 条边连通二分图数量，然后要求出 \(dp_{i,j}\) 为 \(i\) 个点， \(j\) 条边二分图数量，也是枚举 \(1\) 号点连通块大小 \(k\) 和边数 \(a\)，\(dp_{i,j}\) 加上 \(g_{k,a}\times dp_{i-k,j-a}\times \binom{i-1}{k-1}\)。
最后要求序列数量，枚举他用了 \(k\) 种边，容斥掉用了不到 \(k\) 种边的情况就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=35,P=998244353,M=1e6+5;
int n,m,g[N][N*N],f[N][N*N],dp[N][N*N],jc[M],iv[M],inv[M],ans;
int C(int n,int m)
{
if(n<m)
return 0;
return 1LL*jc[n]*iv[m]%P*iv[n-m]%P;
}
int pown(int x,int y)
{
if(!y)
return 1;
int t=pown(x,y>>1);
if(y&1)
return 1LL*t*t%P*x%P;
return 1LL*t*t%P;
}
int main()
{
iv[0]=iv[1]=inv[1]=jc[0]=jc[1]=1;
for(int i=2;i<M;i++)
{
jc[i]=jc[i-1]*1LL*i%P;
inv[i]=1LL*(P-P/i)*inv[P%i]%P;
iv[i]=1LL*iv[i-1]*inv[i]%P;
}
scanf("%d%d",&n,&m);
f[1][0]=g[1][0]=2;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=i*(i+1)/4;j++)
{
for(int k=0;k<=i;k++)
(g[i][j]+=1LL*C(k*(i-k),j)*C(i,k)%P)%=P;
f[i][j]=g[i][j];
for(int k=1;k<i;k++)
{
for(int b=0;b<=k*(k+1)/4&&b<=j;b++)
{
f[i][j]+=P-1LL*f[k][b]*g[i-k][j-b]%P*C(i-1,k-1)%P;
f[i][j]=f[i][j]>=P? f[i][j]-P:f[i][j];
}
}
}
}
for(int i=1;i<=n;i++)
for(int j=0;j<=i*(i+1)/4;j++)
f[i][j]=f[i][j]&1? f[i][j]+P>>1:f[i][j]>>1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i*(i+1)/4;j++)
{
dp[i][j]=f[i][j];
for(int k=1;k<i;k++)
{
for(int b=0;b<=k*(k+1)/4&&b<=j;b++)
{
dp[i][j]+=1LL*f[k][b]*dp[i-k][j-b]%P*C(i-1,k-1)%P;
dp[i][j]=dp[i][j]>=P? dp[i][j]-P:dp[i][j];
}
}
}
}
for(int i=0;i<=n*(n+1)/4;i++)
{
int ret=0;
for(int j=0;j<=i;j++)
(ret+=pown(j,m)*1LL*C(i,j)%P*(i-j&1? P-1:1)%P)%=P;
// printf("%d %d %d\n",i,dp[n][i],ret);
(ans+=1LL*ret*dp[n][i]%P)%=P;
}
printf("%d",ans*1LL*pown(2,m)%P);
}