题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1835
基准时间限制：1 秒
空间限制：131072 KB
初始有n个点，任意两个点之间有一条无向边，现在要移除一些无向边（至少一条），问移除后有恰好m个连通块的方案数是多少。
两个方案不同当且仅当存在至少一条无向边在某个方案中被移除，但是在另一个方案中没被移除。
答案可能很大请模一个998,244,353。
Input
第一行读入n,m。
1<=m<=n<=500
Output
第一行输出方案数。
Input示例
3 2
Output示例
3
题解：
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = ;
const int maxn = ; ll C[maxn][maxn];
void Cmn()//求组合数
{
for(int i=;i<maxn;i++)
{
C[i][]=C[i][i]=;
for(int j=;j<i;j++) C[i][j]=(C[i-][j-]+C[i-][j])%MOD;
}
} ll fpow(ll a,ll b)
{
ll r=,base=a%MOD;
while(b)
{
if(b&) r*=base,r%=MOD;
base*=base;
base%=MOD;
b>>=;
}
return r;
} ll n,m;
ll f[maxn][maxn];
int main()
{
Cmn();
scanf("%d%d",&n,&m); f[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=i;j++)
{
f[i][j]=;
for(int k=;k<=i-(j-);k++)
{
f[i][j] += (C[i-][k-]*f[k][]%MOD)*f[i-k][j-] %MOD;
f[i][j] = f[i][j] % MOD;
}
} f[i][] = fpow(,i*(i-)/);
for(int k=;k<=i;k++) f[i][] = (f[i][] - f[i][k] + MOD) %MOD;
} if(m==) printf("%lld",f[n][]-);
else printf("%lld",f[n][m]);
}
有几个需要注意的点：
1、
对于 for(int k=;k<=i;k++) f[i][] = (f[i][] - f[i][k] + MOD) %MOD;
考虑f[i][j]都是mod过998244353的数，f[i][1] - f[i][k]有可能为负，需要加上MOD后再%MOD；
2、
pow( 2 , i*(i-1)/2 )显然爆longlong，要用矩阵快速幂算；
3、
题目中写“移除一些无向边（至少一条）”，所以当m等于1的时候，不能移除边，就没有方案。