【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;
}
原文地址:http://www.cnblogs.com/AmanoKumiko/p/16875160.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性