专门做图标的网站,创网站软件,网站规划的内容,图片在线设计正题
题目链接:https://atcoder.jp/contests/arc115/tasks/arc115_d 题目大意
给出nnn个点mmm条边的一张无向图#xff0c;对于每个k∈[1,n]k\in[1,n]k∈[1,n] 求恰好有kkk个奇数入度点的生成子图数量。 1≤n,m≤50001\leq n,m\leq 50001≤n,m≤5000 解题思路
考虑有kkk个奇…正题
题目链接:https://atcoder.jp/contests/arc115/tasks/arc115_d 题目大意
给出nnn个点mmm条边的一张无向图对于每个k∈[1,n]k\in[1,n]k∈[1,n] 求恰好有kkk个奇数入度点的生成子图数量。
1≤n,m≤50001\leq n,m\leq 50001≤n,m≤5000 解题思路
考虑有kkk个奇入度点的图有什么性质既然是入度的奇偶性可以从欧拉回路入手。新建一个点向一张有kkk个入度为奇数的点的图上的kkk个点连边那么有且仅有一个方案使得图存在欧拉回路。
所以我们可以先随便向图上的kkk个点连边然后再找图上存在欧拉回路的图的数量。至于怎么寻找存在欧拉回路的图的数量首先我们搞出一棵图的生成树显然树上不存在欧拉回路而所有的环也就是存在欧拉回路的图都可以由每条树边构成的环选出若干个将重复的部分取反得到。
所以nnn个点mmm条边的连通图的欧拉回路数量就是2m−n12^{m-n1}2m−n1如果而我们提前连接了kkk条边的点必须选择所以这些边不会增加欧拉回路的数量所以答案就是(nk)×2m−n1\binom{n}{k}\times 2^{m-n1}(kn)×2m−n1。
然后会发现还是有点问题因为图没有保障连通那么设fif_{i}fi表示目前连接了iii条新边的方案然后每个连通块暴力转移就好了。
时间复杂度O(n2)O(n^2)O(n2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5100,P998244353;
struct node{ll to,next;
}a[N1];
ll n,m,sun,sum,tot,ls[N],C[N][N],pw[N1],f[N];
bool v[N];
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x){v[x]1;sun;for(ll ils[x];i;ia[i].next){sum;if(!v[a[i].to])dfs(a[i].to);}return;
}
signed main()
{scanf(%lld%lld,n,m);for(ll i1,x,y;im;i){scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}C[0][0]pw[0]1;for(ll i1;iN*2;i)pw[i]pw[i-1]*2ll%P;for(ll i1;in;i)for(ll j0;ji;j)C[i][j](C[i-1][j](j?C[i-1][j-1]:0))%P;f[0]1;for(ll i1;in;i)if(!v[i]){sumsun0;dfs(i);sum/2;for(ll jn;j0;j--){if(j1)continue;f[j]f[j]*pw[sum-sun1]%P;for(ll k2;kmin(sun,j);k2)(f[j]f[j-k]*pw[sum-sun1]%P*C[sun][k]%P)%P;}}for(ll i0;in;i)printf(%lld\n,f[i]);return 0;
}
