Update

• 2022-02-10 修改了柿子中的几处小错误，并增加部分说明。

---

前言

校内模拟赛做到这题，我写了一个 $O^* (2^n)$ 的做法，结果发现旁边同学全是状压 dp 的 $O^* (3^n)$ 甚至不知道咋么来的 $O^* (4^n)$ 做法……

那么我是咋做的呢？容斥 + 矩阵树定理。

---

题意简述

给一个节点个数不超过 $10$ 的简单无向图，问有多少棵生成树（有标号）使得它的叶结点个数为 $k$。

---

思路

分类讨论。

特判掉 $n=1,2$ 的情况，这个很好处理。

下面考虑 $n\ge3$ 的情况，此时叶结点个数严格小于 $n$。

---

看到生成树计数就想到矩阵树定理。

但是这有一个 $k$ 个叶子的要求，那咋做哩？

考虑容斥。

我们假设已经钦定了某 $\omega\ \ (\omega<n)$ 个叶结点组合 $a_1,a_2,\dots,a_\omega$。

那么这些叶结点一定和未被钦定的结点相连，每个被钦定的叶结点有一定数量的选法。

对未被钦定的结点跑矩阵树。

由乘法原理，把这些数乘起来，即是对这 $\omega$ 个结点钦定时的方案数 $f_{\{a_\omega\}}$。

我们假设容斥系数是 $S_{\{a_\omega\}}$

考虑每个真正的叶结点方案 $A$ 在哪些钦定 $\{a_\omega\}$ 时被枚举到，有：

$$\sum_\omega\sum_{\{a_\omega\}\subseteq A}S_{\{a_\omega\}}=[|A|=k] $$

我们不难想到对于同样的 $\omega$，其容斥系数相同，即 $S_\omega$。（可以数学归纳法证明）

那么上式即：

$$\sum_\omega\binom{|A|}{\omega}S_\omega=[|A|=k]$$

这个东西是一个二项式反演的形式，我们可以立即得到：

$$S_\omega=(-1)^{\omega-k}\binom\omega k$$

于是答案即：

$$\sum_{k\le|\{a\}|<n}(-1)^{|\{a\}|-k}\binom{|\{a\}|}kf_{\{a\}} $$

枚举所有这样的 $\{a\}$ 就好了。

总复杂度 $O(n^32^n)$，即 $O^* (2^n)$。

---

Code

// 10^8 < 998244353
// 直接在模 998244353 的剩余系下操作
// 钦定叶子，容斥 + 矩阵树即可
// 容斥系数可以二项式反演
// O*(2^n)
// 可以通过

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
template<const ullt p=998244353>
class mod_ullt
{
    private:
        ullt v;
        inline ullt chg(ullt w){return(w<p)?w:w-p;}
        inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
    public:
        mod_ullt():v(0){}
        mod_ullt(ullt v):v(v%p){}
        bol empty(){return!v;}
        inline ullt val(){return v;}
        friend bol operator<(mod_ullt a,mod_ullt b){return a.v<b.v;}
        friend bol operator>(mod_ullt a,mod_ullt b){return a.v>b.v;}
        friend bol operator<=(mod_ullt a,mod_ullt b){return a.v<=b.v;}
        friend bol operator>=(mod_ullt a,mod_ullt b){return a.v>=b.v;}
        friend bol operator==(mod_ullt a,mod_ullt b){return a.v==b.v;}
        friend bol operator!=(mod_ullt a,mod_ullt b){return a.v!=b.v;}
        inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a.v+b.v);}
        inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a._chg(a.v+a.chg(p-b.v));}
        inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a.v*b.v;}
        friend mod_ullt operator/(mod_ullt a,mod_ullt b){return b._power(p-2)*a.v;}
        inline mod_ullt operator-(){return _chg(p-v);}
        mod_ullt sqrt()
        {
            if(power(v,(p-1)>>1,p)!=1)return 0;
            mod_ullt b=1;do b++;while(b._power((p-1)>>1)==1);
            ullt t=p-1,s=0,k=1;while(!(t&1))s++,t>>=1;
            mod_ullt x=_power((t+1)>>1),e=_power(t);
            while(k<s)
            {
                if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
                e=_power(p-2)*x*x,k++;
            }
            return _min(x,-x),x;
        }
        mod_ullt inv(){return _power(p-2);}
        mod_ullt _power(ullt index){mod_ullt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
        voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');v%=p;}
        voi print()
        {
        	static chr C[20];uint tp=0;
        	ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
        	while(tp--)putchar(C[tp]);
        }
        voi println(){print(),putchar('\n');}
        mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
    public:
        inline ullt&operator()(){return v;}
        inline mod_ullt&operator+=(mod_ullt b){return*this=_chg(v+b.v);}
        inline mod_ullt&operator-=(mod_ullt b){return*this=_chg(v+chg(p-b.v));}
        inline mod_ullt&operator*=(mod_ullt b){return*this=v*b.v;}
        mod_ullt&operator/=(mod_ullt b){return*this=b._power(p-2)*v;}
        mod_ullt&operator++(){return v=chg(v+1),*this;}
};
const ullt Mod=998244353;
typedef mod_ullt<Mod>modint;
const uint Siz=35;
struct Mat
{
    modint M[Siz][Siz];uint n;
    Mat():n(0){}
    Mat(uint n):n(n){}
    modint*operator[](uint n){return M[n];}
    voi bzr(){resize(0);}
    voi resize(uint s)
    {
        for(uint i=s;i<n;i++)for(uint j=0;j<n;j++)M[i][j]=M[j][i]=0;
        n=s;
    }
    modint det()
    {
        Mat A=*this;
        modint ans(1);
        for(uint i=0;i<n;i++)
        {
            {
                uint j;for(j=i;j<n&&!A[j][i]();j++);
                if(j==n)return 0;
                if(i!=j)
                {
                    ans=-ans;
                    for(uint k=0;k<n;k++)std::swap(A[i][k],A[j][k]);
                }
            }
            modint qaq=A[i][i];
            ans*=qaq;qaq=qaq.inv();
            for(uint j=0;j<n;j++)A[i][j]*=qaq;
            for(uint j=0;j<n;j++)if(A[j][i]()&&i!=j)
            {
                qaq=A[j][i];
                for(uint k=0;k<n;k++)A[j][k]-=A[i][k]*qaq;
            }
        }
        for(uint i=0;i<n;i++)ans*=A[i][i];
        return ans;
    }
};
typedef std::pair<uint,uint>Pair;
std::vector<Pair>E;
Mat M;
modint P[35],Q[35];
modint binom(uint n,uint m){return P[n]*Q[m]*Q[n-m];}
int main()
{
	P[0]=1;for(uint i=1;i<=30;i++)P[i]=P[i-1]*i;
	Q[30]=P[30].inv();for(uint i=30;i;i--)Q[i-1]=Q[i]*i;
	uint n,m,k;
	scanf("%u%u%u",&n,&m,&k);
	if(n==1)puts(k==1?"1":"0");
	else if(n==2)puts(m==1&&k==2?"1":"0");
	else
	{
		if(!k||k>=n)return puts("0"),0;
		uint u,v;while(m--)scanf("%u%u",&u,&v),E.push_back(Pair(u-1,v-1));
		modint ans;
		for(uint i=0;i<(1u<<n)-1;i++)if(__builtin_popcount(i)>=k)
		{
			modint now;
			std::vector<uint>Leaf,Any,Back(n);
			for(uint j=0;j<n;j++)
				if(i>>j&1)Back[j]=Leaf.size(),Leaf.push_back(j);
				else Back[j]=Any.size(),Any.push_back(j);
			std::vector<modint>Time(Leaf.size());
			M.bzr();
			M.resize(Any.size());
			for(auto e:E)
			{
				if((i>>e.first&1)&&!(i>>e.second&1))
					Time[Back[e.first]]++;
				else if(!(i>>e.first&1)&&(i>>e.second&1))
					Time[Back[e.second]]++;
				else if(!(i>>e.first&1)&&!(i>>e.second&1))
				{
					u=Back[e.first],v=Back[e.second];
					M[u][u]+=1,M[v][v]+=1,
					M[u][v]-=1,M[v][u]-=1;
				}
			}
			M.resize(Any.size()-1);
			now=M.det();
			for(auto t:Time)now*=t;
			uint w=__builtin_popcount(i);
			ans+=((w-k)&1)?-binom(w,k)*now:binom(w,k)*now;
		}
		ans.println();
	}
	return 0;
}