dp
代码
#include<cstdio>
const int N = ;
const int P = ;
int n,m,k,cnt[N];
long long f[N],g[N],o[N],dp[N][];
int e[][],i,j,l,a,b;
int check(int x,int y)
{
int i;
for (i=;i<n;i++)
if ((<<i)==x) break;
int tmp=i,ans=;
for (i=;i<n;i++)
if (((<<i)|y)==y)
ans+=e[tmp][i];
return ans;
}
int main()
{
int test;
scanf("%d",&test);
for (int ii=;ii<=test;ii++)
{
scanf("%d%d%d",&n,&m,&l);
o[]=;for (i=;i<=;i++) o[i]=o[i-]*%P;
for (i=;i<n;i++)
for (j=;j<n;j++)
e[i][j]=;
for (i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
a--;b--;
e[a][b]++;
if (a!=b)
e[b][a]++;
}
for (i=;i<(<<n);i++)
cnt[i]=cnt[i-(i&-i)]+check(i&-i,i);
for (i=;i<(<<n);i++)
f[i]=g[i]=;
for (i=;i<(<<n);i++)
{
j=i;
do
{
j=((j-)&i);
if ((j|(i&-i))==j)
g[i]=(g[i]+g[i-j]*f[j])%P;
}
while (j!=i);
f[i]=(o[cnt[i]]-g[i])%P;
(g[i]+=f[i])%P;
}
for (i=;i<(<<n);i++)
for (k=;k<=l;k++)
dp[i][k]=;
dp[][]=;
for (i=;i<(<<n);i++)
{
for (k=;k<=l;k++)
{
j=i;
do
{
j=((j-)&i);
if ((j|(i&-i))==j)
dp[i][k]=(dp[i][k]+dp[i-j][k-]*f[j])%P;
}
while (j!=i);
}
}
printf("Case #%d:\n%I64d\n",ii,(dp[(<<n)-][l]+P)%P);
}
}