Loading... ## 题意 给定一棵树，有 $n$ 个节点，$n$ 是偶数，每个节点有黑白两种颜色，每种颜色有 $\frac{n}{2}$ 个节点。现在给黑白节点两两配对，问有多少配对情况恰有 $k$ 对黑白节点不为祖先后代关系。 $n\leq 5000$ ## 题解 ### 二项式反演 $$ \begin{align} g_n=\sum_{i=0}^n{n\choose i} f_i \Longleftrightarrow f_n=\sum_{i=0}^n\left(-1\right)^{n-i}{n\choose i}g_i\\ g_k=\sum_{i=k}^n{i\choose k} f_i \Longleftrightarrow f_k=\sum_{i=k}^n\left(-1\right)^{i-k}{i\choose k}g_i \end{align} $$ 组合意义是： 1. 式子一表示： 1. 当 $gi$ 表示至多选 $i$ 个计数； 2. $fi$ 表示恰好 $i$ 同样意义计数。 2. 式子二表示： 1. 当 $gi$ 表示至少选 $i$ 个计数； 2. $fi$ 表示恰好 $i$ 同样意义计数。 证明： 引理： $$ \begin{align} f_n=\sum_{m=0}^n\left[n=m\right]{n\choose m}f_m\\ \sum_{k=0}^n\left(-1\right)^k{n\choose k}=\left[n=0\right] \end{align} $$ 所以有： $$ \begin{align} f_n&=\sum_{m=0}^n\left[n=m\right]{n\choose m}f_m\\ &=\sum_{m=0}^n\sum_{k=0}^{n-m}\left(-1\right)^k{n-m\choose k}{n\choose m}f_m\\ &=\sum_{m=0}^n\sum_{k=0}^{n-m}\left(-1\right)^k{n\choose k}{n-k\choose m}f_m\\ &=\sum_{m=0}^n\left(-1\right)^k{n\choose k}\sum_{k=0}^{n-m}{n-k\choose m}f_m\\ &=\sum_{m=0}^n\left(-1\right)^k{n\choose k}g_{n-k}\\ &=\sum_{i=0}^n\left(-1\right)^{n-i}{n\choose i}g_i \end{align} $$ ### 做题 发现这个题要求恰好为 $k$ 很难搞，所以改成至少为 $k$。然后就简单了，跑树形背包，设 $dp_{u,i}$ 表示以 $u$ 为根的子树内钦定了 $i$ 对，其他不管的方案数。最后取 $dp_{1,k}$ 剩下的部分乱放就可以了。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} #define MODINT_TYPE long long #define barK (64) namespace MODINT{ unsigned long long d; __uint128_t m; inline __attribute((always_inline)) void init(const long long &mod){ m=(((__uint128_t)1)<<barK)/(d=mod); return; } inline __attribute((always_inline)) unsigned long long mod(const unsigned long long &x){ register unsigned long long w=(m*x)>>barK; w=x-w*d; return w>=d?w-d:w; } MODINT_TYPE exgcd(MODINT_TYPE a,const MODINT_TYPE b,MODINT_TYPE &x,MODINT_TYPE &y){ if(!b){ x=1; y=0; return a; } MODINT_TYPE d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } inline __attribute((always_inline)) MODINT_TYPE inv(const MODINT_TYPE &n,const MODINT_TYPE &p){ MODINT_TYPE x,y; exgcd(n,p,x,y); x%=p; return x>=0?x:x+p; } struct MODNUM{ MODINT_TYPE val; inline __attribute((always_inline)) MODNUM(const MODINT_TYPE &x){ if(x<0){ val=d-mod(-x); if(val>=d) val-=d; }else val=mod(x); return; } inline __attribute((always_inline)) MODNUM(){val=0;} inline __attribute((always_inline)) MODNUM operator + (const MODNUM& o) const{return (MODNUM){(val+o.val>=d)?(val+o.val-d):(val+o.val)};} inline __attribute((always_inline)) MODNUM operator + (const MODINT_TYPE& o) const{return *this+MODNUM(o);} friend inline __attribute((always_inline)) MODNUM operator + (const MODINT_TYPE &o,const MODNUM&a){return a+o;} inline __attribute((always_inline)) MODNUM operator - (const MODNUM& o) const{return (MODNUM){(val-o.val<0)?(val-o.val+d):(val-o.val)};} inline __attribute((always_inline)) MODNUM operator - (const MODINT_TYPE& o) const{return *this-MODNUM(o);} friend inline __attribute((always_inline)) MODNUM operator - (const MODINT_TYPE &o,const MODNUM&a){return MODNUM(o)-a;} inline __attribute((always_inline)) MODNUM operator * (const MODNUM& o) const{return (MODNUM){mod(val*o.val)};} inline __attribute((always_inline)) MODNUM operator * (const MODINT_TYPE& o) const{return *this*MODNUM(o);} friend inline __attribute((always_inline)) MODNUM operator * (const MODINT_TYPE &o,const MODNUM&a){return a*o;} inline __attribute((always_inline)) MODNUM operator / (const MODNUM& o) const{return (MODNUM){mod(val*inv(o.val,d))};} inline __attribute((always_inline)) MODNUM operator / (const MODINT_TYPE& o) const{return *this/MODNUM(o);} friend inline __attribute((always_inline)) MODNUM operator / (const MODINT_TYPE &o,const MODNUM&a){return MODNUM(o)/a;} inline __attribute((always_inline)) MODNUM operator ++(){ ++val; if(val>=d) val-=d; return *this; } inline __attribute((always_inline)) MODNUM operator ++(const int){ MODNUM tmp=*this; ++val; if(val>=d) val-=d; return tmp; } inline __attribute((always_inline)) MODNUM operator --(){ --val; if(val<0) val+=d; return *this; } inline __attribute((always_inline)) MODNUM operator --(const int){ MODNUM tmp=*this; --val; if(val<0) val+=d; return tmp; } inline __attribute((always_inline)) MODNUM& operator += (const MODNUM& o) {return *this=*this+o;} inline __attribute((always_inline)) MODNUM& operator += (const MODINT_TYPE& o) {return *this=*this+o;} inline __attribute((always_inline)) MODNUM& operator -= (const MODNUM& o) {return *this=*this-o;} inline __attribute((always_inline)) MODNUM& operator -= (const MODINT_TYPE& o) {return *this=*this-o;} inline __attribute((always_inline)) MODNUM& operator *= (const MODNUM& o) {return *this=*this*o;} inline __attribute((always_inline)) MODNUM& operator *= (const MODINT_TYPE& o) {return *this=*this*o;} inline __attribute((always_inline)) MODNUM& operator /= (const MODNUM& o) {return *this=*this/o;} inline __attribute((always_inline)) MODNUM& operator /= (const MODINT_TYPE& o) {return *this=*this/o;} inline __attribute((always_inline)) operator MODINT_TYPE(){return val;} }; }; MODINT::MODNUM dp[5010][5010],tmp[5010],f[5010]; int siz[5010],sizA[5010]; std::bitset<5010> col; std::vector<int> e[5010]; void dfs(int u,int p){ register int i,j; siz[u]=1,sizA[u]=col[u]; dp[u][0]=1; for(auto v:e[u]) if(v!=p){ dfs(v,u); for(i=0;i<=siz[u];++i) for(j=0;j<=siz[v];++j) tmp[i+j]+=dp[u][i]*dp[v][j]; siz[u]+=siz[v],sizA[u]+=sizA[v]; for(i=0;i<=siz[u];++i) dp[u][i]=tmp[i],tmp[i]=0; } for(i=siz[u];i;--i) dp[u][i]+=dp[u][i-1]*((col[u]?(siz[u]-sizA[u]):sizA[u])-(i-1)); return; } #define PC_DATA_TYPE long long const PC_DATA_TYPE PC_MOD=998244353; const PC_DATA_TYPE PC_DATA_SIZE=1000010; PC_DATA_TYPE inv[PC_DATA_SIZE],fact[PC_DATA_SIZE],invfact[PC_DATA_SIZE]; void init_pc(int n){ register int i; for(inv[0]=0,inv[1]=fact[0]=fact[1]=invfact[0]=invfact[1]=1,i=2;i<=n;++i) invfact[i]=invfact[i-1]*(inv[i]=PC_MOD-PC_MOD/i*inv[PC_MOD%i]%PC_MOD)%PC_MOD,fact[i]=fact[i-1]*i%PC_MOD; return; } PC_DATA_TYPE A(int n,int m){ if(n<0||m<0||n<m) return 0; return fact[n]*invfact[n-m]%PC_MOD; } PC_DATA_TYPE C(int n,int m){ if(n<0||m<0||n<m) return 0; return fact[n]*invfact[n-m]%PC_MOD*invfact[m]%PC_MOD; } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif MODINT::init(998244353); register int i,j,k,u,v; register char c; int n=read(); init_pc(n); for(i=1;i<=n;++i){ loop:c=getchar(); if(c!='0'&&c!='1') goto loop; col[i]=c-'0'; } for(i=1;i<n;++i){ u=read();v=read(); e[u].push_back(v); e[v].push_back(u); } dfs(1,0); for(i=0;i<=n;++i) dp[1][i]*=fact[n/2-i]; for(k=0;k<=n/2;++k){ for(i=k;i<=n;++i) if((i-k)&1) f[k]-=C(i,k)*dp[1][i]; else f[k]+=C(i,k)*dp[1][i]; print(f[k]),putchar('\n'); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改：2024 年 03 月 15 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏