听课笔记 - 2026 重庆 - 06 & 07【Prüfer】【二项式反演】【Min-Max】【范德蒙德卷积】
ExFish
·
2026-01-27 08:22:37
·
算法·理论
orz _Diu_。
二项式反演
\sum_{i=0}^n\binom{n}{i}(-1)^i=[n=0]
就是把贡献全部消掉。当 n=0 的时候只能特殊为 1 ，否则一定能消掉。这是一个定义容斥系数的过程。常用于 DP 的就是：
f_i=\sum_{j=1}^{\infty} \binom{j}{i}g_j \\
g_i=\sum_{j=0}^n(-1)^{n-i}\binom{n}{i}f_i
\\
g_j=\sum_{j=i}^{\infty} \binom{j}{i}(-1)^{j-i}f_j
\small \color{52C41A}[容斥] ARC102C(E) Stop. Otherwise...我们对每一个 p 单独计算贡献，那么不能同时选择 x 和 p-x 。你发现你只关系匹配组数（一定不会重复），考虑插板法。全部选择是 \binom{n+k-1}{k-1} 。我们在不合法匹配中选择一组，总选择就是 \binom{t}{1}\binom{n+k-1-\red 2}{k-1} 。这个减去就是你选择的组也要减去才能选择。
然后我们回到要求的部分，也就是有 0 组不合法的选择骰子方案。我们考虑直接容斥，得出 ans=\sum_{j=0}^t(-1)^j\binom{t}{j}\binom{n-2j+k-1}{k-1} 。
这个做法的本质是：不断减去不要的贡献，再加回多减的部分算出精确贡献 。
::::success[code]
注意 t 与题面中的定义不同，为合法配对数 ，要重新计算，具体见代码。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Math_Limit=1e5+10;
const ll P=998244353;
namespace fish_math{
ll fac[Math_Limit], inv[Math_Limit], fiv[Math_Limit];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
ll Inv(ll x){ return qpow(x,P-2); }
void Init_Math(int lmt){
fac[0]=1, fiv[0]=1;
for(int i=1;i<=lmt;i++)
fac[i]=(fac[i-1]*i)%P,
inv[i]=Inv(i),
fiv[i]=(fiv[i-1]*inv[i])%P;
return;
}
ll C(int n,int m){
if(n<0||m<0||n<m) return 0;
return fac[n]*fiv[m]%P*fiv[n-m]%P;
}
}
using namespace fish_math;
ll k,n,ans;
int main(){
Init_Math(1e5);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>k>>n;
for(ll i=2;i<=2*k;i++){
int t=min(k,i/2)-max(1ll,i-k)+1;
ans=0;
for(int j=0,op=1;j<=t;j++,op=-op)
ans=(ans+op*C(t,j)%P*C(n-2*j+k-1,k-1)%P+P)%P;
cout<<ans<<"\n";
}
return 0;
}::::
\small \color{52C41A}[容斥] \small \color{3498DB}[反演] P6076 染色问题为了避免冲突，颜色数为 c 。
你考虑设一个容斥结果为 f_{i,j,k} 为 i 行不合法，j 列不合法有 k 种颜色不合法的选择数。容斥的式子就是选取 i 行 j 列 k 色，剩下的必须合法，就是剩余格子随机选择。也就有：
f_{i,j,k}=\binom{n}{i}\binom{m}{j}\binom{c}{k}(c-k+1)^{((n-i)(m-j))}。
注意这个时候 f_{0,0,0} 不是直接答案 ，因为这个只是保证不合 法，并不能保证其他都是合法的 ，这里涂色格子考虑了不涂色 。
所以这个时候我们要用二项式反演来算答案，也就是答案为：
ans=\sum_{i=0}^n\sum_{j=0}^m\sum_{k=0}^c(-1)^{i+j+k}f_{i,j,k}
这个其实是三次二项式反演的形式。
::::success[code]
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Math_Limit=1e5+10;
const ll P=1e9+7;
namespace fish_math{
ll fac[Math_Limit], inv[Math_Limit], fiv[Math_Limit];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
ll Inv(ll x){ return qpow(x,P-2); }
void Init_Math(int lmt){
fac[0]=1, fiv[0]=1;
for(int i=1;i<=lmt;i++)
fac[i]=(fac[i-1]*i)%P,
inv[i]=Inv(i),
fiv[i]=(fiv[i-1]*inv[i])%P;
return;
}
ll C(int n,int m){
if(n<0||m<0||n<m) return 0;
return fac[n]*fiv[m]%P*fiv[n-m]%P;
}
}
using namespace fish_math;
ll ans,n,m,c;
int main(){
Init_Math(400);
cin>>n>>m>>c;
for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=c;k++){
int op=((i+j+k)%2)?-1:1;
ans=(ans+op*C(n,i)*C(m,j)%P*C(c,k)%P*qpow(c-k+1,(n-i)*(m-j)%P)%P+P)%P;
}
cout<<ans;
return 0;
}::::
\small \color{52C41A}[容斥] QOJ15623 Charity Raffle / P14686太难了但为什么是蓝题？？？原来是容斥做法太难了。我们被要求求出一个有限制的数列个数，限制是长度、值域以及和限制。然后有一个本题主要难点：第一个最大值后要有 \max 或 \max-1 存在。
正难则反，考虑容斥。这里就考虑最大值唯一且后面的数都 \le \max-2 。通过插板法求出满足条件的全序列个数：
f(n,m,k)=\sum_{i=0}^n(-1)^i\binom{n}{i}\binom{k-im-i+n-1}{n-1}
考虑如何列出反部分的答案，也就可以直接枚举最大值和位置，得：
\sum_{i=0}^m\sum_{j=1}^n\sum_{s=0}^{k-i} f(n-j,i-2,s)f(j-1,i-1,k-i-s)
展开这玩意然后再整理能得出一坨，可以去看题解。最后得出答案为 f(n,m,k)-f(n,m-1,k-1) 。
::::success[code]
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll Test;
const int Math_Limit=5e6+10;
const ll P=998244353;
namespace fish_math{
ll fac[Math_Limit], inv[Math_Limit], fiv[Math_Limit];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
ll Inv(ll x){ return qpow(x,P-2); }
void Init_Math(int lmt){
fac[0]=1, fiv[0]=1;
for(int i=1;i<=lmt;i++)
fac[i]=(fac[i-1]*i)%P,
inv[i]=Inv(i),
fiv[i]=(fiv[i-1]*inv[i])%P;
return;
}
ll C(ll n,ll m){
if(n<0||m<0||n<m) return 0;
return fac[n]*fiv[m]%P*fiv[n-m]%P;
}
}
using namespace fish_math;
ll n,m,k;
ll f(ll n,ll m,ll k){
ll ans=0;
for(int i=0;i<=n;i++){
int op=(i%2)?-1:1;
ans=(ans+op*C(n,i)*C(k-m*i-i+n-1,n-1)%P+P)%P;
}
return ans;
}
int main(){
Init_Math(5e6);
cin>>n>>k>>m;
cout<<(f(n,m,k)-f(n,m-1,k-1)+P)%P;
return 0;
}::::
\min-\max 容斥也就是求一个集合的最大值，基本形式：见学习笔记。
证明：对于 S 中每一个数 x 设为 k 大，考虑何时作为 \min(T) ：当且仅当 T 中所有元素都比 x 大。也就是有贡献：
\sum_{i=0}^{k-1}(-1)^i\binom{k-1}{i}=[k=1]
这个式子就是说在比 x 大的数中容斥来算贡献。这样 \max(S) 就转为了 \min(S) 。
好像没什么用？？但是这个在期望下生效，也就是 E(\max(S))=\sum_{T\in S,T\neq \emptyset} (-1)^{|T|-1}E(\min(T)) 。
于是就可以做下一道题了。
\small \color{52C41A}[容斥] QOJ15299 Vertex Cover设 t_i 为 i 点第一次被染黑的时间。设每条边是 u_i,v_i 那么就要求 E(\max(S)),S=\set{\min(t_{u_i},t_{v_i})} 。
使用 \min-\max 容斥，得：
E(\max(S))=\sum_{T\in S,T\neq \empty} (-1)^{|T|-1}E(\min(T))
合并 \min 得 \min(T)=\min(t_x|(x=u_i \vee x=v_i),i\in T) 这么个抽象东西，变为求 T 有关点第一个被染黑的期望时间。这个时候就把问题转化为了一个点问题。
设 k=|T| ，我们要求覆盖的期望时间。我们使用 trick：第一次出发局面期望时间为每个时刻没被出发的概率和 。骗你的其实是第一次合出 Super 的概率为之前每个 Att 没有合出的概率和。显然有一个时刻没有被触发的概率为 (\frac{n-k}{n})^i ，也就是每次都 \sout{99\%} 。容易知道和就是：
E(\min(T))=\sum_{i\ge 0} (\frac{n-k}{n})^i=\frac{n}{k}
然后考虑如何求解 E(\max(S)) ，这一步直接枚举显然是不行的，但是可以考虑树上背包。f_{u,i,0/1} 为 u 子树内选择 i 以及 u 的选择情况。
显然有转移：
\begin{aligned}
f'_{u,i,k}f_{v,j,l} &\to f_{u,i+j,k} \\
-f'_{u,i,k}f_{v,j,l} &\to f_{u,i+j+2-k-l,1}
\end{aligned}
::::success[code]
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e3+10;
const ll P=998244353;
ll f[N][N][2],g[N][2];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
int n,sz[N]; vector<int>e[N];
void dfs(int p,int fa){
sz[p]=1, f[p][0][0]=1;
for(auto v:e[p])if(v^fa){
dfs(v,p);
sz[p]+=sz[v];
for(int i=0;i<=sz[p];i++) g[i][0]=g[i][1]=0;
for(int i=0;i<=sz[p]-sz[v];i++){
for(int j=0;j<=sz[v];j++){
(g[i+j][0]+=f[p][i][0]*(f[v][j][0]+f[v][j][1])%P)%=P;
(g[i+j][1]+=f[p][i][1]*(f[v][j][0]))%=P;
(g[i+j+1][1]-=(f[p][i][1]*f[v][j][0]%P+f[p][i][0]*f[v][j][1]%P)%P-P)%=P;
(g[i+j+2][1]-=(f[p][i][0]*f[v][j][0])%P-P)%=P;
}
}
for(int i=0;i<=sz[p];i++)
f[p][i][0]=g[i][0],
f[p][i][1]=g[i][1];
}
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v),
e[v].push_back(u);
}
dfs(1,0);
ll ans=0;
for(int i=2;i<=n;i++)
ans=(ans+(f[1][i][0]+f[1][i][1])%P*qpow(i,P-2)%P)%P;
cout<<(P-ans*n%P)%P ;
return 0;
}::::
\small \color{52C41A}[容斥] P7247 教材运输同样是一道 \min-\max 。设 S 为代价集合，答案就是 E(\max(S)) 。然后我们转化为 E(\min(T)) 为走到 T 中一点的期望代价。然后直接 DP。
设 f_{T,u} 为从 u 第一次标记到 T 任意节点的期望代价，有转移：
nf_{T,u}=\sum_{v=1}^n f_{T,v}+d_{u,v}\ (u\notin T)
你发现这个东西循环了。所以考虑列方程。
先设等式右侧有 w_u=\sum_{v=1}^n d_{u,v} 。我们列出 n-m 个 nf_{T,u}-\sum_{v=1}^n f_{T,v}=w_u 等式，其余均为 0 。我们加和 s=\sum_{v=1}^n f_{T,v} ，发现答案为 E(\min(T))=f_{T,1}=\frac{s+w_1}{m} 。最后求出所有 w_u 可以求出答案为：
\begin{aligned}
ans&=\sum_{T}=(-1)^{|T|-1}E(\min(T)) \\
&=\sum_{T}(-1)^{|T|-1}(\frac{w_1}{n}+\frac{\sum_{u\notin T}w_u}{n|T|}) \\
&=\sum_{m=1}^{n-1}(-1)^{m-1}(\frac{w_1}{n}\binom{n-1}{m}+\frac{1}{nm}\binom{n-2}{m}\sum_{u=2}^nw_u)
\end{aligned}
不像人。
::::success[code]
乐子卡牛魔常呢。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Math_Limit=1e6+10;
const ll P=998244353;
namespace fish_math{
ll fac[Math_Limit], inv[Math_Limit], fiv[Math_Limit];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
ll Inv(ll x){ return qpow(x,P-2); }
void Init_Math(int lmt){
fac[0]=1, fiv[0]=1;
for(int i=1;i<=lmt;i++)
fac[i]=(fac[i-1]*i)%P,
inv[i]=Inv(i),
fiv[i]=(fiv[i-1]*inv[i])%P;
return;
}
ll C(ll n,ll m){
if(n<0||m<0||n<m) return 0;
return fac[n]*fiv[m]%P*fiv[n-m]%P;
}
}
template<typename type>
inline void read(type &x){
x=0;bool flag(0);char ch=getchar();
while(!isdigit(ch))flag=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
flag?x=-x:0;return;
}
template<typename type>
inline void write(type x){
x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
do Stack[++top]=x%10,x/=10; while(x);
while(top) putchar(Stack[top--]|48);
}
using namespace fish_math;
const int N=1e6+10;
int n;
ll a[N],sz[N],su[N],W1,Ws,dis[N];
vector<pair<int,ll>>e[N];
void dfs(int p,int fa){
sz[p]=1, su[p]=a[p];
for(auto v:e[p])if(v.first^fa){
dfs(v.first,p);
sz[p]+=sz[v.first];
su[p]=(su[p]+su[v.first])%P;
}
return;
}
void dfs2(int p,int fa){
W1=(W1+(dis[p]*a[p])%P)%P;
for(auto v:e[p])if(v.first^fa){
dis[v.first]=(dis[p]+v.second)%P;
dfs2(v.first,p);
Ws=(Ws+v.second*((sz[v.first]*(su[1]-su[v.first]+P)%P+su[v.first]*(sz[1]-sz[v.first]+P)%P)%P))%P;
}
return;
}
int main(){
read(n);
Init_Math(n);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<n;i++){
int u,v,w;
read(u),read(v),read(w);
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dfs(1,0); dfs2(1,0);
Ws=(Ws-W1+P)%P;
ll ans=0;
for(int m=1;m<n;m++){
int op=(m%2)?1:-1;
ans=(ans+(op+P)%P*(C(n-1,m)*W1%P+inv[m]*((C(n-1,m)*W1%P+C(n-2,m)*Ws%P)%P)%P)%P+P)%P;
}
write(ans*Inv(n)%P);
return 0;
}::::
底下这个做法的实现难度差不多但是好想，就不给代码了。
然后老师还要讲一个简单的做法，就是设 f_{i,0/1} 为 i 个未标记点，0 为根节点，1 表示随机选点计算完成的代价，有转移：
$y$：从随机一个点走回根的期望代价。
$z$：从一个非根点走到另一个非根点的代价。
$$
f_{i,0}=\frac{i}{n-1}f_{i=1,1}+\frac{n-1-i}{n-1}f_{i,1}+x\\
f_{i,1}=\frac{i}{n-1}f_{i-1,1}+\frac{1}{n-1}f_{i,0}+\frac{n-2-i}{n-1} f_{i,1}+\frac{1}{n-1}y+\frac{n-2}{n-1}z
$$
### $\small \color{52C41A}[容斥]$ QOJ3275 小明的树 / P8990
点边容斥也是容斥。对于一颗树，点数等于边数加一。我们要统计连通块，那么考虑统计没点亮的点构成的连通块，没点亮的两头减去两头都没被点亮的边数为 $1$。
考虑如何维护。可以用线段树维护每个事件的状况。维护 $d_i$ 为暗点连通块个数。$l_i$ 为亮点连通块个数。然后线段树维护两个值的最小值，操作的本质就是区间加。
正如不知道上面那题怎么评的蓝，这题是怎么评的黑的。
::::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10;
int n,m,p[N],q[N],u[N],v[N];
ll su[N<<2]; int mn[N<<2],mc[N<<2],tc[N<<2],ts[N<<2];
void pushup(int p){
mn[p]=min(mn[p<<1],mn[p<<1|1]);
su[p]=mc[p]=0;
if(mn[p]==mn[p<<1])
mc[p]+=mc[p<<1], su[p]+=su[p<<1];
if(mn[p]==mn[p<<1|1])
mc[p]+=mc[p<<1|1], su[p]+=su[p<<1|1];
return;
}
void pushdown(int p){
if(tc[p]){
tc[p<<1]+=tc[p];
tc[p<<1|1]+=tc[p];
mn[p<<1]+=tc[p];
mn[p<<1|1]+=tc[p];
tc[p]=0;
}
if(ts[p]){
ts[p<<1]+=ts[p];
ts[p<<1|1]+=ts[p];
su[p<<1]+=(ll)mc[p<<1]*ts[p];
su[p<<1|1]+=(ll)mc[p<<1|1]*ts[p];
ts[p]=0;
}
return;
}
void build(int p,int l,int r){
if(l==r){
mc[p]=1; mn[p]=n-l+(n==l);
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return;
}
void update(int p,int l,int r,int ql,int qr,int ux,int uy){
if(ql<0||qr>n||ql>qr) return;
if(ql<=l&&r<=qr){
tc[p]+=ux;
ts[p]+=uy;
mn[p]+=ux;
su[p]+=(ll)mc[p]*uy;
return;
}
pushdown(p);
int mid=(l+r)>>1;
if(ql<=mid)
update(p<<1,l,mid,ql,qr,ux,uy);
if(qr>mid)
update(p<<1|1,mid+1,r,ql,qr,ux,uy);
pushup(p);
return;
}
void upd(int l,int r,int k){
l=q[l], r=q[r];
if(l>r) swap(l,r);
update(1,1,n,1,l-1,-k,0);
update(1,1,n,l,r-1,0,k);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
q[1]=n;
for(int i=1;i<n;i++)
cin>>u[i]>>v[i];
for(int i=1;i<n;i++)
cin>>p[i], q[p[i]]=i;
p[n]=1;
build(1,1,n);
for(int i=1;i<n;i++)
upd(u[i],v[i],1);
cout<<su[1]<<"\n";
while(m--){
int u1,v1,u2,v2;
cin>>u1>>v1>>u2>>v2;
upd(u1,v1,-1);
upd(u2,v2,1);
cout<<su[1]<<"\n";
}
return 0;
}
```
::::
### $\small \color{52C41A}[容斥]$ QOJ1838 Intellectual Implementation
困难容斥吧我觉得。首先我们提出一个叫做**网格容斥**的东西：被这个矩形包含的**格子数**减去**相邻两个网格图的数量**加上**田子网格数量**为 $1$。这是和一位呢？$nm-(n-1)m-n(m-1)+(n-1)(m-1)=1$。
然后我们考虑如何查询。我们用上述容斥式子来转化得出询问**有交矩形面积和**。我们可以通过统计 $\binom{k}{2}$ 和 $\binom{k}{3}$。扫描线维护即可，但是真的很难写。
### $\small \color{3498DB}[反演]$ P6478 游戏
问题：$m$ 组匹配 $k$ 各组祖先后代的方案数 $g_k$。然后设 $f_k$ 为 $k$ 个匹配是合法的。你发现这两个式子符合二项式反演，所以可以通过 $f$ 来求 $g$。设 $dp_{u,i}$ 为 $u$ 处理完了 $i$ 组完成匹配的情况。
对于转移直接树上背包转移，然后答案就是 $f_k=dp_{1,k}
\binom{n}{k}(n-k)!$，注意有匹配可以乱选。复杂度 $\mathcal O(n^2)$。
### $\small \color{52C41A}[容斥]$ 反射容斥 P3266 骗我呢
有两条拦着问路径数的题。考虑将军饮马把折线转正成直线。在每一次碰到直线的时候都在字符串 $S$ 后加一个字符 `A` 或 `B`，然后就可以根据 `A` 和 `B` 来容斥了，这就是反射容斥。
::::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
const int Math_Limit=5e6+10;
const ll P=1e9+7;
namespace fish_math{
ll fac[Math_Limit], inv[Math_Limit], fiv[Math_Limit];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
ll Inv(ll x){ return qpow(x,P-2); }
void Init_Math(int lmt){
fac[0]=1, fiv[0]=1;
for(int i=1;i<=lmt;i++)
fac[i]=(fac[i-1]*i)%P,
inv[i]=Inv(i),
fiv[i]=(fiv[i-1]*inv[i])%P;
return;
}
ll C(ll n,ll m){
n+=m;
if(n<0||m<0||n<m) return 0;
return fac[n]*fiv[m]%P*fiv[n-m]%P;
}
}
using namespace fish_math;
int n,m;
pair<int,int>dot;
void flip(int x){ dot={dot.se-x,dot.fi+x}; }
int main(){
Init_Math(5e6);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
int x=1, y=-m-2;
dot={n+m+1,n};
ll ans=C(dot.fi,dot.se);
int op=-1;
while(dot.fi>=0&&dot.se>=0){
flip(x);
(ans+=op*C(dot.fi,dot.se)+P)%=P, op*=-1;
flip(y);
(ans+=op*C(dot.fi,dot.se)+P)%=P, op*=-1;
}
dot={n+m+1,n};
op=-1;
while(dot.fi>=0&&dot.se>=0){
flip(y);
(ans+=op*C(dot.fi,dot.se)+P)%=P, op*=-1;
flip(x);
(ans+=op*C(dot.fi,dot.se)+P)%=P, op*=-1;
}
cout<<ans;
return 0;
}
```
::::
### Prüfer 序列
可以将带标号的树转化为一个唯一的整数序列，就是 Prüfer 序列。
做法：每次选择一个**编号最小的叶子节点删去**，记录它链接到的节点，最后只会剩下 $2$ 个节点。复杂度 $\mathcal O(n\log n)$。或者也有指针做法能做到 $\mathcal O(n)$。
这个序列有一定有点为 $n$ 以及每个节点出现的次数为度数 $-1$，也就是不含叶子。
同理，我们可以用 Prüfer 序列重建树。每次选一个最小编号的度数为 $1$ 的点与枚举到的 Prüfer 序列的点连接，并同时减去度。最后会剩下两个度数为 $1$ 的点，一个为 $n$。可以用堆 $\mathcal O(n\log n)$。
这个东西有一个有用的推论：$n$ 点无向图，$k$ 个大小为 $a_1,\dots,a_k$ 的连通块，添加 $k-1$ 条边使得整张图联通的方案是 $n^{k-2}\prod_{i=1}^ka_i$。
### P2290 树的计数
根据 Prüfer 的意义计算出答案为：
$$
\frac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}
$$
注意计算的时候要用高精度，为什么不带取模呢。
::::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=155;
int n,d[N],s;
int h[N],box[N][N],su[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>d[i], s+=d[i]-1;
if(s!=n-2) return cout<<0,0;
if(n==1) return cout<<(d[1]==0?1:0),0;
if(n==2) return cout<<((d[1]==1&&d[2]==1)?1:0),0;
for(int i=2;i<=n;i++){
int c=i;
for(int j=2;j*j<=c;j++)if(c%j==0)
while(c%j==0) box[i][j]++, c/=j;
if(c) box[i][c]++;
}
for(int i=1;i<=n-2;i++)
for(int j=2;j<=150;j++)
su[j]+=box[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=d[i]-1;j++)
for(int k=2;k<=150;k++)
su[k]-=box[j][k];
ll mul=1;
for(int i=2;i<=150;i++){
for(int j=1;j<=su[i];j++)
mul*=i;
}
cout<<mul;
return 0;
}
```
::::
### 范德蒙德卷积
~~NOIP 2025 T2。~~
我们有：
$$
\sum_i\binom{i}{n}\binom{k-i}{m}=\binom{k+1}{n+m+1}
$$
这个东西的组合意义是从 $0$ 到 $k$ 中选择一个 $i$ 必选前面选 $n$ 个后面选 $m$ 个，也可以直接选择。
### $\small \color{FFC116}[组合]$ CF785D Anton and School - 2
范德蒙德卷积的模板题。问合法的子序列个数。我们考虑类似范德蒙德卷积一样选择一个中点来计算。考虑用最后一个 `(` 的位置，整个合法的有 $a$ 个 `(`，右边有 $b$ 个 `)`，那么有：
$$
\sum_{i=0}^{\min(a-1,b-1)}\binom{a-1}{i}\binom{b}{i+1}
$$
我们修改一下：
$$
\sum_{i=0}^{\min(a-1,b-1)}\binom{a-1}{a-1-i}\binom{b}{i+1}
$$
这个使用的是组合数的对称性。
然后就得出答案：
$$
\binom{a+b-1}{a}
$$
::::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Math_Limit=2e5+10;
const ll P=1e9+7;
namespace fish_math{
ll fac[Math_Limit], inv[Math_Limit], fiv[Math_Limit];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
ll Inv(ll x){ return qpow(x,P-2); }
void Init_Math(int lmt){
fac[0]=1, fiv[0]=1;
for(int i=1;i<=lmt;i++)
fac[i]=(fac[i-1]*i)%P,
inv[i]=Inv(i),
fiv[i]=(fiv[i-1]*inv[i])%P;
return;
}
ll C(ll n,ll m){
if(n<0||m<0||n<m) return 0;
return fac[n]*fiv[m]%P*fiv[n-m]%P;
}
}
using namespace fish_math;
int n,sr,l,r;
ll ans;
string s;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Init_Math(2e5);
cin>>s; n=s.size(); s=" "+s;
for(int i=1;i<=n;i++)
if(s[i]==')') ++sr;
for(int i=1;i<=n;i++){
l+=(s[i]=='('), r+=(s[i]==')');
if(s[i]=='(')ans=(ans+C(l+sr-r-1,l))%P;
}
cout<<ans;
return 0;
}
```
::::
### QOJ15036 Tree and Subgraph Problem
这是一个树上的连通块计数，我们选择一个基准防止记重。直接选择会有一条路径记录计算重复。我们使用颜色来考虑。首先我们枚举 $u$ 讨论另一个连通块在哪里。
- 在子树：统计子节点选择点集的方案数，且去除点集后再选择一个包含 $u$ 的点集方案数。
- 否则：统计 $u$ 子树内选择包含 $u$ 的点集的方案数，并在子树外选择一颗子树的方案数。
可以使用各种数据结构来维护。
### $\small \color{FFC116}[组合]$ CF708E Student's Camp
风只能摧毁左侧和右侧。那么我们显然可以直接列出一行在 $k$ 天消失 $i$ 个的概率：
$$
\binom{k}{i}p^i(1-p)^{k-i}
$$
也就是可以选择一些天来消失。最后一定会成为一些区间。之后我们尝试 DP，可以考虑设 $f_{i,j}$ 为 $i$ 行右端点 $r$，$0$ 到 $i$ 连通的概率。
转移枚举左端点，可以求不相交的方案并减去。此时判断 $r'<l$ 或 $l'<r$ 即可判断方案。
转移如下：
$$
f_{i,r}=\sum_{l=1}^r p_{l-1}p_{m-r}\left(\sum_{j=1}^m f_{i-1,j}-\sum_{j=1}^{l-1}f_{i-1,j}-\sum_{j=1}^{m-r} f_{i-1,j}\right)
$$
后面两个减号就是所有符合条件的值减去了两个断开的方案。
然后考虑用前缀和维护 $sf_{j}=\sum_{i=1}^j f_{i-1,j}$。这个式子就会变为：
$$
f_{i,r}=\sum_{l=1}^r p_{l-1}p_{m-r}(sf_{m}-sf_{l-1}-sf_{m-r})
$$
然后我们拆项得：
$$
p_{m-r}\left(\left(sf_m-sf_{m-r}\right)\sum_{l=1}^rp_{l-1}-\sum_{l=1}^rsf_{l-1}p_{l-1}\right)
$$
这个还是可以前缀和优化。$sp_l=\sum_{i=1}^l p_i$。$ss_l=\sum_{i=1}^l sf_{l}p_l$。
最后我们有答案：
$$
f_{i,r}=p_{m-r}((sf_m-sf_{m-r})sp_{r-1}-ss_{r-1})
$$
::::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1550;
#define ll long long
const int Math_Limit=1e5+10;
const ll P=1e9+7;
namespace fish_math{
ll fac[Math_Limit], inv[Math_Limit], fiv[Math_Limit];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
ll Inv(ll x){ return qpow(x,P-2); }
void Init_Math(int lmt){
fac[0]=1, fiv[0]=1;
for(int i=1;i<=lmt;i++)
fac[i]=(fac[i-1]*i)%P,
inv[i]=Inv(i),
fiv[i]=(fiv[i-1]*inv[i])%P;
return;
}
ll C(ll n,ll m){
if(n<0||m<0||n<m) return 0;
return fac[n]*fiv[m]%P*fiv[n-m]%P;
}
}
using namespace fish_math;
ll p1,k,a,b,n,m;
ll p[N],sp[N],f[N][N],sf[N],ss[N],su;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Init_Math(1e5);
cin>>n>>m>>a>>b>>k;
p1=Inv(b)*a%P;
for(ll i=0;i<=min(k,m);i++)
p[i]=C(k,i)*qpow(p1,i)%P*qpow((1-p1+P)%P,k-i)%P;
for(ll i=0;i<=m;i++)
sp[i]=((i>0?sp[i-1]:0)+p[i])%P;
f[0][m]=1;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++)
sf[j]=(sf[j-1]+f[i-1][j])%P,
ss[j]=(ss[j-1]+p[j]*sf[j]%P)%P;
for(ll j=1;j<=m;j++)
f[i][j]=p[m-j]*(((sf[m]-sf[m-j]+P)%P)*sp[j-1]%P-ss[j-1]+P)%P;
}
for(int j=1;j<=m;j++)
su=(su+f[n][j])%P;
cout<<su;
return 0;
}
```
::::
### $\small \color{52C41A}[容斥]$ LOJ3399 Communication Network
这个题是给你一棵树，然后要你求出所有的生成树与原树边集的并集大小 $x$ 的 $x2^x$ 之和。这个值看起来很奇怪，我们也不会做。
我们可以使用子集容斥的方法，也就是 $f(S)=\sum_{T\in S}\sum_{T'\in T}(-1)^{T-T'}f(T')$。这个可以用二项式定理来证明。
考虑如何使用这个东西。首先有 $f(S)=|S|2^{|S|}$。
那么就有：
$$
\begin{aligned}
原式&=\sum_{S_2}f(S_1\cap S_2) \\
&= \sum_{S_2}\sum_{S\in(S_1\cap S_2)} \sum_{T\in S} (-1)^{|S|-|T|}f(T) \\
&= \sum_{S\in S_1}\sum_{T\in S}(-1)^{|S|-|T|}f(T)(\sum_{S\in S_2}1) \\
&=\sum_{S\in S_1}(-1)^{|S|}|S|\sum_{i=0}^{|S|-1}(-2)^{i+1}\binom{|S|-1}{i}(\sum_{S\in S_2}1) \\
&=\sum_{S\in S_1}(-1)^{|S|}(-2)|S|\sum_{i=0}^{|S|-1}(-2)^{i}\binom{|S|-1}{i}(\sum_{S\in S_2}1) \\
&=\sum_{S\in S_1}2|S|(\sum_{S\in S_2}1)
\end{aligned}
$$
有结论：$r$ 个连通块，每个大 $a_i$，总生成树个为 $n^{r-2}\prod^r_{i=1}r_i$，答案就转化为 $2\frac{1}{n^2}\prod_{i=1}^r na_i\sum_{S\in S_1}|S|
这个东西的组合意义就是划分树，每个连通块选择点产生 n 的贡献，求所有选法的贡献之和。然后 DP 设 f_{u,0/1,0/1} 为 u 子树是否选点以及是否贡献，转移是容易的。
这里还用到了组合数的吸收公式：
m\binom{n}{m}=n\binom{n-1}{m-1}
证明是容易的，直接大力展开即可。
::::success[code]
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
#define ll long long
#define rep(i) for(int (i)=0;(i)<3;(i)++)
const ll P=998244353;
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
int n;
ll f[N][2][2],g[2][2];
vector<int>e[N];
void dfs(int p,int fa){
f[p][0][0]=1;
f[p][1][0]=n; // Choosen, times n
for(auto v:e[p])if(v^fa){
dfs(v,p);
rep(i) rep(j) g[i][j]=0;
rep(x) rep(y) rep(i) rep(j){
if(i+x>1||j+y>1) continue;
(g[i+x][j+y]+=f[p][x][y]*f[v][i][j]%P)%=P;
}
rep(x) rep(i){
if(i+x>1) continue;
(g[i+x][1]+=f[p][x][0]*f[v][i][0]%P)%=P;
}
rep(x) rep(y) rep(j){
if(j+y>1) continue;
(g[x][j+y]+=f[p][x][y]*f[v][1][j]%P)%=P;
}
rep(i) rep(j) f[p][i][j]=g[i][j];
}
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
cout<<2*qpow(n,P-3)%P*f[1][1][1]%P;
return 0;
}::::
### $\small \color{FFC116}[组合]$ QOJ15446 Count Triangular Sequences
这个题就是直接计数比较困难所以考虑差分计数。原始序列 $\set{a_i}$，然后我们差分考虑是 $d_i=a_i-a_{i-1}-a_{i-2}$。这样我们就有 $a_i=\sum_{j=1}^n fib_j\times d_{i+1-j}$（打表观察）。最后直接背包制作即可。
::::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=30;
#define ll long long
const int Math_Limit=2e5+10;
const ll P=1e9+7;
namespace fish_math{
ll fac[Math_Limit], inv[Math_Limit], fiv[Math_Limit];
ll qpow(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;
return res;
}
ll Inv(ll x){ return qpow(x,P-2); }
void Init_Math(int lmt){
fac[0]=1, fiv[0]=1;
for(int i=1;i<=lmt;i++)
fac[i]=(fac[i-1]*i)%P,
inv[i]=Inv(i),
fiv[i]=(fiv[i-1]*inv[i])%P;
return;
}
ll C(ll n,ll m){
if(n<0||m<0||n<m) return 0;
return fac[n]*fiv[m]%P*fiv[n-m]%P;
}
}
using namespace fish_math;
int n,m;
ll ans,f[N],dp[M][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Init_Math(2e5);
cin>>n;
f[1]=1;
for(int i=2;;i++){
f[i]=f[i-1]+f[i-2];
if(f[i]>n){ m=i; break; }
}
dp[1][0]=1;
for(int i=1;i<=n;i++)
ans=(ans+qpow(n,i))%P;
for(int i=1;i<=min(n,m);i++){
for(int j=0;j<=n;j++){
(dp[i+1][j]+=dp[i][j])%=P;
if(j+f[i]>n) continue;
(dp[i][j+f[i]]+=dp[i][j])%=P;
if(j+f[i]+f[i-1]<=n)
ans=(ans-fac[i]*dp[i][j]%P+P)%P;
else
ans=(ans-inv[2]*fac[i]%P*dp[i][j]%P+P)%P;
}
}
cout<<ans;
return 0;
}
```
::::