网站打开的速度慢,中企动力做网站怎么样,周年庆网站要怎么做,wordpress获取不同分类文章正题
题目链接:https://ac.nowcoder.com/acm/contest/24346/L 题目大意
有一张2n2n2n个点的完全图#xff0c;在上面删除一棵生成树#xff0c;然后求这张图的完全匹配方案数。 1≤n≤20001\leq n\leq 20001≤n≤2000 解题思路
考虑容斥#xff0c;可以dpdpdp出fi,j,0/1f…正题
题目链接:https://ac.nowcoder.com/acm/contest/24346/L 题目大意
有一张2n2n2n个点的完全图在上面删除一棵生成树然后求这张图的完全匹配方案数。
1≤n≤20001\leq n\leq 20001≤n≤2000 解题思路
考虑容斥可以dpdpdp出fi,j,0/1f_{i,j,0/1}fi,j,0/1表示iii的子树中有jjj条边必须匹配当前点有/没有匹配的方案这个可以通过枚举子树大小做到O(n2)O(n^2)O(n2)
然后除了已经匹配的点剩下的点可以任意匹配考虑2n2n2n个点的完全图的匹配方案我们可以先选出nnn个点放在左边然后剩下的任意匹配但是注意到会重复每一边都可以选择交换所以会被算重2n2^n2n次所以方案就是 (2nn)×n!2n\frac{\binom{2n}{n}\times n!}{2^n}2n(n2n)×n!
然后如果指定了kkk条边必选那么容斥系数就是(−1)k(-1)^k(−1)k就好了。
时间复杂度O(n2)O(n^2)O(n2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4100,P998244353;
struct node{ll to,next;
}a[N1];
ll n,tot,ls[N],fac[N],inv[N],pw[N];
ll f[N][N/2][2],g[N/2][2],siz[N],ans;
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){siz[x]1;f[x][0][0]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);for(ll j0;j(siz[x]siz[y])/2;j)g[j][0]g[j][1]0;for(ll j0;jsiz[x]/2;j)for(ll k0;ksiz[y]/2;k){(g[jk][0]f[x][j][0]*(f[y][k][0]f[y][k][1])%P)%P;(g[jk][1]f[x][j][1]*(f[y][k][0]f[y][k][1])%P)%P;(g[jk1][1]f[x][j][0]*f[y][k][0]%P)%P;}siz[x]siz[y];for(ll j0;jsiz[x]/2;j)f[x][j][0]g[j][0],f[x][j][1]g[j][1];}return;
}
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
ll Mac(ll n)
{return C(n*2,n)*fac[n]%P*pw[n]%P;}
signed main()
{scanf(%lld,n);nn*2;fac[0]inv[0]inv[1]pw[0]1;for(ll i2;iN;i)inv[i]P-inv[P%i]*(P/i)%P;for(ll i1;iN;i)pw[i]pw[i-1]*inv[2]%P;for(ll i1;iN;i)fac[i]fac[i-1]*i%P,inv[i]inv[i-1]*inv[i]%P;for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dfs(1,0);for(ll i0;in/2;i){ll w(f[1][i][0]f[1][i][1])%P;ww*Mac(n/2-i)%P;(ans(i1)?(P-w):w)%P;}printf(%lld\n,ans);return 0;
}
