2021 ICPC 沈阳L Perfect Matchings 【容斥+树形dp】
题意：从一个含有2*n个点的完全图中删去一棵树，问在剩下点中选取n条边，使得这n条边为独立集的选法有多少种。
想法：一般这种让你求选某个特定的值的题目的时候，如果没有好的切入点，就要想到容斥。那么这题我们怎么用容斥来思考呢。既然不让我们选树边，那我们就反其道而行之，强行选树边,那么：
ans=(选取0条树边的方案)（剩下2n个点的完全图任选n条边的方案）
-(选取1条树边的方案)（剩下2n-2个点的完全图任选n-1条边的方案）
+(选取2条树边的方案)（剩下2n-4个点的完全图任选n-2条边的方案）
....(选取k条树边的方案)（剩下2n-2*k个点的完全图任选n-k条边的方案）
那么我们分布思考，先考虑如何求选取k条树边的方案，这个可以使用树形dp实现。我们设 为以i为根下选取了j条树边，其中根节点i选或者不选（请记住，我们要保证选取的树边也是相互独立的）。
考虑如何进行状态转移，容易想到一共有3种转移方式:
- 将u和子树v合并，u包含i条树边，v包含j条树边，不选u:
- 将u和子树v合并，u包含i条树边，v包含j条树边，选u:
- 将u和子树v合并，u包含i条树边，v包含j条树边，将u和v连边:
以上我们便完成了树形dp的部分
接下来就是在图里选边了，我们已经知道被选取了k条树边，那我们手里还剩 个点，从这些点中我们要分成2组，组成条边 ,那么结果就是,由于对于一组边，左右交换属于重复计算，那么我们需要除掉重复的部分，去重这个属于高中的知识了，除以即可
综上，我们便完成了此题，接下来只要将代码实现即可，这题数据范围比较小，只要正常写法都能过
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define set9 fixed<<setprecision(9)
#define set12 fixed<<setprecision(12)
#define set2 fixed<<setprecision(2)
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define db double
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=2e5+5;
const ll mod=998244353;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
// inline ll Inverse(ll x) { return qpow(x,mod-2);}
ll fact[maxn],inv[maxn];
ll f[4005][2005][3],sz[4005],t[2005][3],pw2[2005];
inline ll Inverse(ll x) { return qpow(x,mod-2);}
inline ll C(ll n,ll m) { if(m>n||m<0) return 0; return fact[n]*inv[m]%mod*inv[n-m]%mod;}
void init(int n)
{
ll f=1;
fact[0]=inv[0]=1;
pw2[0]=1;
for(int i=1;i<=n;i++)
{
f=f*i%mod;
fact[i]=f;
pw2[i]=(pw2[i-1]*2ll)%mod;
}
inv[n]=qpow(f,mod-2);
for(int i=n-1;i>=1;i--)
{
inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
}
vector<int>g[4005];
void dfs(int u,int fa)
{
f[u][0][0]=1;
sz[u]=1;
for(auto v:g[u])
{
if(v==fa) continue;
dfs(v,u);
//第一种写法，使用过渡数组
// memset(t,0,sizeof t);//过渡数组
// rep(i,0,sz[u]/2)
// {
// rep(j,0,sz[v]/2)
// {
//
// f[u][i+j][0]=(f[u][i+j][0]+f[u][i][0]*(f[v][j][0]+f[v][j][1])%mod)%mod;
// f[u][i+j][1]=(f[u][i+j][1]+f[u][i][1]*(f[v][j][0]+f[v][j][1])%mod)%mod;
// f[u][i+j+1][1]=(f[u][i+j+1][1]+f[u][i][0]*f[v][j][0]%mod)%mod;
// }
// }
// for(int i=0;i<=sz[u]/2+sz[v]/2+1;i++)
// f[u][i][0]=t[i][0],f[u][i][1]=t[i][1];
//第二种写法，倒序枚举，更快，但是要注意细节
per(i,sz[u]/2,0)
{
per(j,sz[v]/2,0)// rep(j,0,sz[v]/2)
{
if(j)
{
f[u][i+j][0]=(f[u][i+j][0]+f[u][i][0]*(f[v][j][0]+f[v][j][1])%mod)%mod;
f[u][i+j][1]=(f[u][i+j][1]+f[u][i][1]*(f[v][j][0]+f[v][j][1])%mod)%mod;
}
f[u][i+j+1][1]=(f[u][i+j+1][1]+f[u][i][0]*f[v][j][0]%mod)%mod;
}
}
sz[u]+=sz[v];
}
}
signed main()
{
int n=read();
init(2*n+5);
rep(i,1,2*n-1)
{
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
int flag=1,ans=0;
rep(i,0,n)
{
int cnt=(f[1][i][0]+f[1][i][1])%mod;
int num=n-i,num_2=2ll*num;
int val=(C(num_2,num)*fact[num])%mod;
val=(val*Inverse(pw2[num]))%mod;
val=(cnt*val)%mod;
ans=(ans%mod+flag*val+mod)%mod;
flag*=-1;
}
printf("%lld\n",ans);
}
作业帮二面29人在聊
查看27道真题和解析
