【题解】CF2174F Mosaic Tree

题意：

给定正整数 \(n\) 和 \(m\) 。有 \(n\) 个编号为 \(1,\dots,n\) 的顶点，给定它们的颜色。现在需要对 \(n\) 个点构造一棵无向树。给定长度为 \(m\) 的二进制数组 \(\mathrm{mask}=(\mathrm{mask}_1,\dots,\mathrm{mask}_m)\)，其中每个 \(\mathrm{mask}_i\in{0,1}\)。

对于每个颜色 \(i\)，要求所有颜色为 \(i\) 的顶点的度数之和的奇偶性等于 \(\mathrm{mask}_i\) 。

计算满足上述条件的有标号树的数量，结果对 \(10^9+7\) 取模。

\(1\leq n,m\leq 10^4\) ，\(1\leq c_i\leq m\)

题解：

\(prufer\) 序列告诉我们，可以将 \(n\) 个点的树与长为 \(n-2\) 的值域 \([0,n]\) 的数列构成双射。不难发现，如果已经确定了度数序列 \(d_1,\cdots d_n\) ，那么 \(i\) 会在这个数列中出现 \(d_i-1\) 次，因此树的数量是多重组合数 \(\displaystyle \binom{n-2}{d_1-1,\cdots, d_n-1}=\frac{(n-2)!}{(d_1-1)!\cdots(d_n-1)!}\) 。

我们只关心分母的贡献。对第 \(c\) 个颜色，有一个度数总和奇偶性的限制，假设所有颜色为 \(c\) 的下标为共有 \(t\) 个，且第 \(c\) 个颜色最后的度数总和为 \(s\geq t\) ，那么分母的贡献可以写成：

\[\begin{aligned} &[x^s](\sum_{d\geq1}\frac{x^d}{(d-1)!})^t\\ =&[x^s](\sum_{d\geq0}\frac{x^d}{d!}\cdot x)^t\\ =&[x^s](x\cdot e^x)^t\\ =&[x^{s-t}] e^{xt} \end{aligned} \]

\(s-t\) 取遍所有的非负奇数/非负偶数，故颜色 \(c\) 的生成函数根据奇偶性可以写成 \(\displaystyle\frac{e^{xt}\pm e^{-xt}}{2}\) 。

对于所有颜色，我们将它们的生成函数乘起来，最后每一项都是 \(e^{xi}\) 的形式，可以用背包把最后 \(e^{xi}\) 前的系数算出来，记为 \(c_i\) 。

注意到 \(s-t\) 的总和为 \(2(n-1)-n=n-2\) ，故最终分母的总贡献为：

\[\begin{aligned} &[x^{n-2}]\sum_{j=-n}^n c_je^{xj}\\ =&\sum_{j=-n}^n c_j[x^{n-2}]e^{xj}\\ =&\sum_{j=-n}^nc_j\cdot\frac{j^{n-2}}{(n-2)!} \end{aligned} \]

把这个式子再乘上最开始分子的 \((n-2)!\) ，答案即为 \(\displaystyle\sum_{j=-n}^n c_j\cdot j^{n-2}\) 。

注意 \(n=1\) 需要特判，总复杂度 \(O(nm)\) ，需要适当卡常。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){ll x=0; bool f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=0; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}return f?x:-x;
}
inline void write(ll x){if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar('0'+x%10);
}
struct Mod{ll m,p;void init(ll pp){m=((__int128)1<<64)/pp;p=pp;}ll operator()(ll x){return x-((__int128(x)*m)>>64)*p;}
} mod;
const ll MOD=1e9+7;
const ll inv2=(MOD+1)/2;
const ll N=10009;
ll n,m;
ll c[N],msk[N],cnt[N];
ll coef[2][2*N];
inline ll qpow(ll a,ll b,ll MOD){ll res=1;while(b){if(b&1) res=(res*a)%MOD;b>>=1;a=(a*a)%MOD;}return res;
}
void solve(){n=read(),m=read();for(ll i=1;i<=m;i++) cnt[i]=0;for(ll i=1;i<=n;i++){c[i]=read();cnt[c[i]]++;}for(ll i=1;i<=m;i++){msk[i]=read();}if(n==1){for(ll i=1;i<=m;i++){if(msk[i]%2==1){puts("0");return;}}puts("1");return;}for(ll j=-n;j<=n;j++) coef[0][j+n]=0;coef[0][n]=1;for(ll i=1;i<=m;i++){for(ll j=-n;j<=n;j++) coef[i&1][j +n]=0;for(ll j=-n;j<=n;j++){if(j-cnt[i]>=-n)(coef[i&1][j +n]+=coef[i&1^1][j-cnt[i] +n]);}if(msk[i]%2!=cnt[i]%2){for(ll j=-n;j<=n;j++){if(j+cnt[i]<=n)(coef[i&1][j +n]+=MOD-coef[i&1^1][j+cnt[i] +n]);}}else{for(ll j=-n;j<=n;j++){if(j+cnt[i]<=n)(coef[i&1][j +n]+=coef[i&1^1][j+cnt[i] +n]);}}for(ll j=-n;j<=n;j++) coef[i&1][j +n]=mod(coef[i&1][j +n]*inv2);}ll ans=0;for(ll j=-n;j<=n;j++){ll cur=coef[m&1][j +n];ans+=cur*qpow((MOD+j)%MOD,n-2,MOD)%MOD;ans%=MOD;}write(ans),puts("");
}
int main(){mod.init(MOD);ll T=read();while(T--){solve();}return 0;
}