ZR 集训 Day15 - 组合数学

前言 B 班太难了，回 C 班了。。。 二项式反演 二项式反演经常被使用于那些求恰好为 n 个的方案数的问题。 常用形式： g_n 表示至多 n 个的方案，f_n 表示恰好 n 个的方案： gn=∑i=0n(ni)fi⟺fn=∑i=0n(−1)n−i(ni)gig_n = \sum_{i = 0}^{n} {n \choose i}f_i\iff f_n = \sum_{i = 0}^{n} (-1)^{n-i}{n \choose i} g_i g_n 表示至少 n 个的方案，f_n 表示恰好 n 个的方案： gn=∑i=nm(in)fi⟺fn=∑i=nm(−1)i−n(in)gig_n=\sum_{i=n}^m {i \choose n} f_i \iff f_n=\sum_{i=n}^m (-1)^{i-n} {i \choose n} g_i Prufer 序列 看图示： 代码： C++ void prufer(){ int p=1,lf; for(int i=1;i `void prufer(){ int p=1,lf; for(int i=1;in;i++) deg[i]++,deg[fa[i]]++; while(deg[p]!=1) p++; lf=p; for(int i=1;in-1;i++){ pru[i]=fa[lf],deg[fa[lf]]--; if(deg[fa[lf]]==1&&fa[lf]p) lf=fa[lf]; else{ p++; while(deg[p]!=1) p++; lf=p; } } }` 代码： C++ void invprufer(){ int p=1,lf; for(int i=1;i `void invprufer(){ int p=1,lf; for(int i=1;in-1;i++)deg[pru[i]]++; for(int i=1;in;i++) deg[i]++; while(deg[p]!=1) p++; lf=p; for(int i=1;in-1;i++){ fa[lf]=pru[i],deg[fa[lf]]--; if(deg[fa[lf]]==1&&fa[lf]p) lf=fa[lf]; else{ p++; while(deg[p]!=1) p++; lf=p; } } fa[lf]=n; }` 题单 文艺计算姬 可以从 Prufer 序列的角度计算，因为 Prufer 序列最后会剩下一条边，这条边肯定是连接二分图左右两边的，因此左右两边每一边分别删掉了 n-1 和 m-1 个点，每删一边的点就会把另一边的点记录到 Prufer 序列中，所以左右两边的贡献乘一起为 n^{m-1}\times m^{n-1}。 代码： C++ #include using namespace std; #define int long long int n,m,q; __int128 qpow(__int128 x,__int128 y){ __int128 res=1; while(y){ if(y&1) (res*=x)%=q; (x*=x)%=q,y>>=1; } return res; } signed main(){ cin>>n>>m>>q; cout `#include using namespace std; #define int long long int n,m,q; __int128 qpow(__int128 x,__int128 y){ __int128 res=1; while(y){ if(y&1) (res*=x)%=q; (x*=x)%=q,y>>=1; } return res; } signed main(){ cin>>n>>m>>q; cout(int)(((__int128)qpow(n,m-1)*(__int128)qpow(m,n-1))%q); return 0; }` CF997C Sky Full of Stars 二维二项式反演题。 设 f_{i,j} 为至少有 i 行 j 列颜色相同的方案数，g_{i,j} 为恰好有 i 行 j 列颜色相同的方案数。 有： f_{x,y} = \sum_{i=x}^n \sum_{j=y}^n \binom{i}{x}\binom{j}{y} g_{i,j} \iff g_{0,0} = \sum_{i=0}^n \sum_{j=0}^n (-1)^{i+j} f_{i,j} 分类讨论 f_{i,j} 的取值： 当 i, j \neq 0 时：f_{i,j} = \binom{n}{i}\binom{n}{j} \cdot 3^{(n-i)(n-j)+1} 当 ij = 0, i+j \neq 0 时：f_{i,0} = f_{0,i} = \binom{n}{i} \cdot 3^{i+n(n-i)} 当 i = j = 0 时：f_{0,0} = 3^{n^2} \begin{aligned} g_{0,0} &= \sum_{i=1}^n \sum_{j=1}^n (-1)^{i+j} f_{i,j} + 2 \sum_{i=1}^n (-1)^i f_{i,0} + f_{0,0} \\ &= \sum_{i=1}^n \sum_{j=1}^n (-1)^{i+j} \binom{n}{i}\binom{n}{j} \cdot 3^{(n-i)(n-j)+1} + 2 \sum_{i=1}^n (-1)^i \binom{n}{i} \cdot 3^{i+n(n-i)} + 3^{n^2} \\ &= 3^{n^2+1} \sum_{i=1}^n \binom{n}{i} (-1)^i 3^{-in} \left( (1 - 3^{i-n})^n - 1 \right) + 2 \cdot 3^{n^2} \left( (1 - 3^{1-n})^n - 1 \right) + 3^{n^2} \end{aligned} 代入 ans = 3^{n^2} - g_{0,0}，抵消 3^{n^2} 后得到最终公式： ans = -3^{n^2+1} \sum_{i=1}^n \binom{n}{i} (-1)^i 3^{-in} \left( (1 - 3^{i-n})^n - 1 \right) - 2 \cdot 3^{n^2} \left( (1 - 3^{1-n})^n - 1 \right) 代码： C++ #include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int n,ans,a,b; int jie[N],inv[N]; int qpow(int x,int y){ int res=1; ((x%=mod)+=mod)%=mod; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } void init(){ jie[0]=1; for(int i=1;i=0;i--) (inv[i]=inv[i+1]*(i+1))%=mod; } int chose(int n,int m){ return jie[n]*inv[n-m]%mod*inv[m]%mod; } signed main(){ cin>>n; init(); for(int i=1;i `#include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int n,ans,a,b; int jie[N],inv[N]; int qpow(int x,int y){ int res=1; ((x%=mod)+=mod)%=mod; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } void init(){ jie[0]=1; for(int i=1;in;i++) (jie[i]=jie[i-1]*i)%=mod; inv[n]=qpow(jie[n],mod-2); for(int i=n-1;i>=0;i--) (inv[i]=inv[i+1]*(i+1))%=mod; } int chose(int n,int m){ return jie[n]*inv[n-m]%mod*inv[m]%mod; } signed main(){ cin>>n; init(); for(int i=1;in;i++){ int c=chose(n,i), d=qpow(qpow(3,i*n),mod-2), e=qpow(qpow(3,n-i),mod-2), f=qpow(mod-e+1,n)-1, num=c*d%mod*f%mod; if(i&1) (a-=num)%=mod; else (a+=num)%=mod; } (a*=qpow(3,n*n+1))%=mod; int c=qpow(qpow(3,n-1),mod-2), d=(qpow(mod-c+1,n)-1)%mod; b=d*2%mod*qpow(3,n*n)%mod; ans=(a+b)%mod; cout(mod-ans)%mod; return 0; }` P6086 【模板】Prüfer（Prufer）序列 模板，上面有代码，这里不赘述了。 P12639 [UOI 2020] Topological Sorting of a Tree 考虑容斥： 容斥公式： \text{答案} = \sum_{T \subseteq S} (-1)^{|T|} \cdot N(T) 其中 N(T) 表示：将 T 中的边强制变成 `解释： 对于一条内向边 u > v： 不放入 T：这条边被拆掉，u 和 v 分属不同连通块，彼此无大小约束。 放入 T：这条边被强制变成 ` 设 f_{u,i} 为在 u 子树中，u 所在连通块大小为 i 的带容斥系数方案数之和。 从叶子向上合并，枚举当前 u 的连通块大小 i 和子节点 v 的连通块大小 j。 记组合数 C = \binom{sz_u + sz_v}{sz_u}，表示将两棵子树的拓扑序交错合并的方案数（内部顺序不变，从总位置中选 sz_u 个给 u 子树的节点）。 外向边 ``：两种选择对应容斥 $f'{u,i} = f'{u,i} +f_{u,i} \times f_{v,j} \times C \quad $ $f'{u,i+j} = f'{u,i+j}-(f_{u,i} \times f_{v,j} \times C) \quad $ 合并完所有子节点后，根据拓扑序公式除以连通块大小：f_{u,i} \leftarrow f_{u,i} \times i^{-1} 最终答案为：\text{ans} = \sum_{i=1}^n f_{1,i} 代码（这题三倍经验）： C++ #include using namespace std; #define int long long const int N=3005; const int mod=1e9+7; int n,ans; int dp[N][N],C[N][N],f[N],siz[N],inv[N]; struct node{ int v; bool w; }; vector t[N]; void init(){ inv[1]=1; for(int i=2;i>n; init(); for(int u=2;u>v>>w; t[v].push_back({u,w=='>'}); } dfs(1); for(int i=1;i `#include using namespace std; #define int long long const int N=3005; const int mod=1e9+7; int n,ans; int dp[N][N],C[N][N],f[N],siz[N],inv[N]; struct node{ int v; bool w; }; vectornode> t[N]; void init(){ inv[1]=1; for(int i=2;in;i++) (inv[i]=(mod-mod/i)*inv[mod%i])%=mod; C[0][0]=1; for(int i=1;in;i++){ C[i][0]=1; for(int j=1;ji;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } } void dfs(int u){ dp[u][1]=siz[u]=1; for(auto[v,w]:t[u]){ dfs(v); for(int i=1;isiz[u];i++) for(int j=1;jsiz[v];j++){ if(w){ (f[i]+=dp[u][i]*dp[v][j]%mod*C[siz[u]+siz[v]][siz[v]])%=mod; ((f[i+j]-=dp[u][i]*dp[v][j]%mod*C[siz[u]+siz[v]][siz[v]]%mod)+=mod)%=mod; } else (f[i+j]+=dp[u][i]*dp[v][j]%mod*C[siz[u]+siz[v]][siz[v]])%=mod; } siz[u]+=siz[v]; for(int i=1;isiz[u];i++){ dp[u][i]=f[i]; f[i]=0; } } for(int i=1;isiz[u];i++) (dp[u][i]*=inv[i])%=mod; } signed main(){ cin>>n; init(); for(int u=2;un;u++){ int v; char w; cin>>v>>w; t[v].push_back({u,w=='>'}); } dfs(1); for(int i=1;in;i++) (ans+=dp[1][i])%=mod; coutans; return 0; }`