【CF53E】Dead Ends
Description
给出\(n\)个点\(m\)条边的无向图,求恰有\(k\)个叶子的连通图个数
Input
一行三个数\(n,m,k\)
然后\(m\)行读入图
Output
一行一个数表示答案
Sample Input
3 3 2
1 2
2 3
1 3
Sample Output
3
Data Constraint
\(1\le n\le 10\)
Solution
提供现代科技的爆标做法
使用集合幂级数,并定义乘法为子集卷积
用二项式反演,然后变成求一个导出子图的生成树的方案数
考虑一个一个点加入(也就是逐点牛顿迭代法)
那么新的方案数显然就是对原图做\(\exp\)(带上连通块和新点之间的边数的乘积)
于是复杂度就是\(O(n^22^n)\)
Code
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define mo 998244353
#define LL long long
#define N 15
int n,m,k,len,e[N],f[1<<N],g[1<<N][N],res[1<<N],ans,w[N],C[N][N],inv[N];
int count(int x){return x?count(x>>1)+(x&1):0;}
int mi(int x,int y){
if(y==1)return x;
return y&1?1ll*x*mi(1ll*x*x%mo,y/2)%mo:mi(1ll*x*x%mo,y/2);
}
int mod(int x){return x>=mo?x-mo:x;}
void FMT(int lg,int sz,int x){
F(i,0,lg-1) for(int j=0;j<sz;j+=(1<<i+1)){
F(k,j,j+(1<<i)-1) F(d,0,lg)g[k|(1<<i)][d]=mod(g[k|(1<<i)][d]+(x==1?g[k][d]:mo-g[k][d]));
}
}
void Exp_GF(int*A,int lg){
F(i,0,lg)res[i]=0;
res[0]=1;
F(i,1,lg){
F(j,1,i)res[i]=mod(res[i]+1ll*res[i-j]*A[j]%mo*j%mo);
res[i]=1ll*res[i]*inv[i]%mo;
}
F(i,0,lg)A[i]=res[i];
}
void Exp(int lg,int sz){
FMT(lg,sz,1);
F(i,0,sz-1)Exp_GF(g[i],lg);
FMT(lg,sz,-1);
}
void solve(){
f[0]=1;
F(i,0,n-1){
F(j,0,(1<<i)-1) F(k,0,i)g[j][k]=0;
F(j,0,(1<<i)-1)g[j][count(j)]=f[j]*count(e[i+1]&j);
Exp(i,1<<i);
F(j,1<<i,(1<<i+1)-1)f[j]=g[j^(1<<i)][count(j)-1];
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
F(i,1,n)inv[i]=mi(i,mo-2);
len=1<<n;
F(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
e[u]|=(1<<v-1);
e[v]|=(1<<u-1);
}
solve();
F(i,0,len-1){
LL tmp=1;
F(j,1,n)if(!((1<<j-1)&i))tmp=tmp*count(e[j]&i);
w[n-count(i)]+=f[i]*tmp;
}
F(i,0,n)C[i][0]=1;
F(i,1,n) F(j,1,i)C[i][j]=C[i-1][j]+C[i-1][j-1];
F(i,k,n)ans+=C[i][k]*(i-k&1?-1:1)*w[i];
printf("%d",ans);
return 0;
}
标签:Ends,int,mo,Dead,CF53E,1ll,define
From: https://www.cnblogs.com/AmanoKumiko/p/16875160.html