首页 > 其他分享 >【CF53E】Dead Ends

【CF53E】Dead Ends

时间:2022-11-09 21:14:29浏览次数:41  
标签:Ends int mo Dead CF53E 1ll define

【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

相关文章

  • HDU 5874 Friends and Enemies
    ProblemDescriptionOnanisolatedisland,livedsomedwarves.Aking(notadwarf)ruledtheislandandtheseasnearby,thereareabundantcobblestones......
  • TestDeadLock
    publicclassTestDeadLockimplementsRunnable{intb=100;//成员变量,一个方法改变了值就是永远改变了publicsynchronizedvoidm1()throwsException{b=1000......
  • ybt 1459:friends
     写下一个字符串A,将其复制一遍得到B,在任意位置(包括首尾)插入一个字符得到C。现在你得到C。求出A 题意中的 [复制]:这个多余的字符在[1,md]或[md,n]枚举这个......
  • 配置Nginx遇到Active:inactive (dead)解决方法
    问题:●nginx.service-nginx-highperformancewebserverLoaded:loaded(/lib/systemd/system/nginx.service;enabled;vendorpreset:enabled)Acti......
  • Java中extends和implements区别【杭州多测师】【杭州多测师_王sir】
    extends与implements的不同1、在类的声明中,通过关键字extends来创建一个类的子类。一个类通过关键字implements声明自己使用一个或者多个接口。extends是继承某个类,继承......
  • [luogu6575]Friends
    记$s=p+q$,当存在一个点度数$\ges$时,显然无解记$d_{S,T}=\sum_{x\inS,y\inT}[(x,y)\inE]$,称$S\subseteqV$合法当且仅当$|S|\lep$且$d(S,V\backslashS)\leq$结论:若......
  • csu 1552: Friends 二分图 + Miller_Rabin
    ​​http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1552​​把那n个数写两次,分成相同的两堆,判断相加是质数的,连一条边,然后找最大匹配,ans=最大匹配/2做的时候一直......
  • 继承extends
    继承extends关键字extends,语法:publicclass子类名extends父类{}子类继承了父类的成员(排除private修饰成员,以及父类的构造方法)子类也叫派生类,父类也叫基类。j......
  • Python startswith()和endswith()方法
    除了前面介绍的几个方法外,Python 字符串变量还可以使用startswith()和endswith()方法。startswith()方法startswith()方法用于检索字符串是否以指定字符串开头,如果......
  • python爬取“舔狼”语录-助你520之前找到girlfriends
    ......