@exut 2024-10-15T01:29:51.000000Z 字数 4232 阅读 181

10.3 组合数学专题训练

组合数学 刷题

A [ARC110D] Binomial Coefficient is Fun

题目描述

我们有一个包含 $N$ 个非负整数的序列 $A$ 。

对于所有长度为 $N$ 且和不超过 $M$ 的非负整数序列 $B$ ，求 $\prod_{i = 1}^N {B_i \choose A_i}$ 之和，对 $(10^9 + 7)$ 取模。

$1 \le N \le 2000$
$1 \le M \le 10^9$
$0 \le A_i \le 2000$

sol

$\prod_{i = 1}^N {B_i \choose A_i}=\dfrac{\prod_{i=1}^{N} B_i!}{ \prod_{i=1}^{N}(B_i-A_i)!}\times\dfrac{1}{\prod_{i=1}^{N} A_i!}$

后半部分可以预处理。

考虑题目除了 $\sum B \le M$ 还有什么约束，其实还有 $\forall 1\le i \le N,A_i\le B_i$ ，不然这一段乘起来是 $0$ 没有贡献。

然后发现这样并不能做出来，化不下去了，脑子不够想不出组合意义。

遂挂一篇生成函数的博客在这里，没学完生成函数。

啊于是就可以生成函数搞一下？

考虑 ${i\choose j}$ 的生成函数 $F_j(x)=\sum_{i=0}^{\infty} {i \choose j}x^i$ 。

现在考虑把 $F_j$ 跟 $F_{j-1}$ 之类的挂上关系，求一个通项公式。

简单推导（把 $\sum$ 的上下界省略了）：

$F_j(x)=\sum_{i=0}^{\infty} {i \choose j}x^i\\ =\sum {i-1\choose j}x^i+\sum{i-1\choose j-1}x^i\\ =xF_j(x)+xF_{j-1}(x)$

（关于 $i-1$ ，其实只需要换个元就可以化成 $i$ 的形式了）

啊于是说我们得到一个式子 $F_j(x)=\frac{x}{1-x}F_{j-1}(x)$ 。

然后稍微推一下通项，带入求 $F_0$ 然后算：

$F_0=\sum x^i=\frac{1}{1-x}\\ F_j=(\frac{x}{1-x})^j F_0=\frac{x^j}{(1-x)^{j+1}}$

同时有结论 $F_a(x)F_b(x)=F_{a+b}(x)\frac{1}{1-x}$ ，带入即证。

答案的计算就可以用一个式子：

$S=\sum a_i\\ \sum_{j=S}^{M} [x^j] \prod F_{a_i}(x)\\ =\sum_{j=S}^{M} [x^j] F_S(x)\frac{1}{(1-x)^{n-1}}\\ =\sum_{j=0}^{M-S} [x^j] \frac{1}{(1-x)^{S+n}}$

然后根据广义二项式定理有一个经典的结论：

$\frac{1}{(1-x)^n}=\sum_{k=0}^{\infty}{n+k-1\choose k}x^k$

于是乎答案就是：

$\sum_{j=0}^{M-S} {S+n+j-1\choose j}\\ =\sum_{j=0}^{M-S} {S+n+j-1\choose S+n-1}\\$
由组合恒等式：

$\sum_{l=0}^{n} {l\choose k}={n+1\choose k+1}$

所以答案就是

${M+n\choose S+n}$ 算就行了，相信少爷机）

C Anton and School - 2

Anton and School - 2

给定一个长度为 $n$ 的括号序列，求该括号序列满足如下条件的子序列个数：
1. 长度为正偶数
2. 假设该子序列长度为 $2m$ ，则该子序列前 $m$ 个均为 (，后 $m$ 个均为 )。

对 $10^9+7$ 取模。

$n \le 2 \times 10^5$ 。

sol

wok C明显比 B 简单。

看到子序列考虑枚举最后一个 $（$ 并强制爱选取，从而保证不重不漏。

然后这个 $（$ 左边有 $a$ 个 $($ （包括自己），右边有 $b$ 个 $)$ ，那么它对答案的贡献就是

$\sum_{i=0}^{a-1}{a-1\choose i}{b\choose i+1}$

上界不需要和 $b$ 取小，因为多的部分是 $0$ 没有影响。

然后发现这玩意复杂度有点寄

考虑化一下式子

$\sum_{i=0}^{a-1}{a-1\choose i}{b\choose i+1}\\ =\sum_{i=0}^{a-1}{a-1\choose a-(i+1)}{b\choose i+1}\\$

然后用一下范德蒙德卷鸡

答案就是

$a+b-1\choose a$ 对于每个

$($ 算一遍就行

E 游戏

sol

恰好是一个很烦的限制，我们可以考虑用二项式反演来搞掉。

设 $g_k$ 表示钦定 $k$ 对点构成祖先后代关系的方案数， $f_k$ 表示恰好。

容易发现

$g_k=\sum_{i=k}^m {i\choose k}f_i$ 然后反演一下可得

$f_k=\sum_{i=k}^m(-1)^{i-k}{i\choose k}g_i$

于是问题从一个恰好问题变成了一个至少问题，一下就好多了pwp

看看怎么算 $g_k$

设 $dp_{u,j}$ 表示在 $u$ 为根的子树内钦定 $j$ 个祖先后代匹配的方案数。

转移分两步吧，一个树形背包

把各个子树的答案（就是不算 $u$ 自己）的答案合并
单独考虑 $u$ 分颜色讨论

第一种式子是 $dp[i][j+k]=\sum_{son}dp[i][j]\times dp[son][k]$ ，然后这依托看起来 $n^3$ 的式子其实是 $n^2$ 的，很遗憾我不会证明，就这样吧

第二种就是子树内跟 $u$ 同颜色的点的个数

$g_k=dp[1][k]\times(\frac{n}{2}-k)!$ ，即剩下的自由组合

反演即可

真的难写难调，放个码这题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=5e3+5,mod=998244353;
int frac[MAXN], invfrac[MAXN], inv[MAXN];
inline int C(int n, int m) { return frac[n] * invfrac[m] % mod * invfrac[n - m] % mod; }
void init(int Max) {
    frac[0]=invfrac[0]=1;
    frac[1]=invfrac[1]=inv[1]=1;
    for(int i=2;i<=Max;i++){
        frac[i]=frac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        invfrac[i]=invfrac[i-1]*inv[i]%mod;
    }
}
struct edge{
    int v,nxt;  
}e[MAXN*2];
int hd[MAXN],tot;
char s[MAXN];
int n,m;
void add(int u,int v){
    e[++tot]={v,hd[u]},hd[u]=tot;
}
int A[MAXN],B[MAXN];
void dfs(int now,int fa){
    if(s[now]=='0') A[now]++;
    else B[now]++;
    for(int i=hd[now];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa)continue;
        dfs(v,now);
        A[now]+=A[v];
        B[now]+=B[v];
    }
}
int siz[MAXN];
int dp[MAXN][MAXN];
int f[MAXN],g[MAXN];
void sol(int now,int fa){
    siz[now]=0;
    dp[now][0]=1;
    for(int i=hd[now];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa)continue;
        sol(v,now);
        for(int j=0;j<=siz[now]+siz[v];j++){
            g[j]=0;
        }
        for(int j=0;j<=siz[now];j++){
            for(int k=0;k<=siz[v];k++){
                g[j+k]=(g[j+k]+(dp[now][j]*dp[v][k]%mod))%mod;
            }
        }
        siz[now]+=siz[v];
        for(int j=0;j<=siz[now];j++)
            dp[now][j]=g[j];
    }
    if(s[now]=='0'){
        for(int i=siz[now];i>=0;i--){
            if(B[now]-i>0) dp[now][i+1]=(dp[now][i+1]+dp[now][i]*(B[now]-i)%mod)%mod;
        }            
        if (dp[now][siz[now]+1]) siz[now]++;
    }
    else{
        for(int i=siz[now];i>=0;i--){
            if(A[now]-i>0) dp[now][i+1]=(dp[now][i+1]+dp[now][i]*(A[now]-i)%mod)%mod;
        }
        if (dp[now][siz[now]+1]) siz[now]++;
    }
}
signed main(){
    cin>>n;
    init(n);
    m=n/2;
    cin>>(s+1);
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);add(y,x);
    }
    dfs(1,0);
    sol(1,0);
    for(int i=0;i<=siz[1];i++)
    g[i]=dp[1][i]*frac[m-i]%mod;
    for(int i=0;i<=m;i++){
        for(int j=i,op=1;j<=siz[1];j++,op=-op){
            f[i]=(f[i]+op*C(j,i)*g[j]%mod+mod)%mod;
        }
        cout<<f[i]<<"\n";
    }
}

G BBQ Hard

组合意义天地灭，代数推导保平安！

[AGC001E] BBQ Hard

题面翻译

有 $n$ 个数对 $(a_i, b_i)$ ，求出

$\sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j}$

答案对 $10 ^ 9 + 7$ 取模。

sol

先考虑把限制削弱一下：

$\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j}$ 最后除以

$2$ 就行了

然后就是大家都喜欢的暴算时间，设 $t_i=a_i+b_i$

$\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j}\\ =\sum_{i=1}^{n}\sum_{j=1}^{n}[x^{a_i+a_j}](x+1)^{t_i+t_j}\\ =[x^0]\sum_{i=1}^{n}\sum_{j=1}^{n}x^{-a_i-a_j}(x+1)^{t_i+t_j}$
没写完先发出来吧

TO BE UPD