## 1 > 有两个序列，一个序列长度为 $n$ 的序列，一个序列长度为 $m$，每个数均在 $0,1$ 中随机取，求两个序列的和相等的方案数。 假设 $n<m$，可以列出最朴素的式子 $$ ANS=\sum_{i=0}^n\binom{n}{i}\binom{m}{i} $$ 若第一个序列有 $x$ 个 $1$ 和 $n-x$ 个 $0$，则第二个序列必须有 $x$ 个 $1$ 和 $m-x$ 个 $0$。 考虑对第二个序列进行反转，则第二个序列对应的新序列有 $m-x$ 个 $1$ 和 $x$ 个 $0$。 问题转化成一个长度为 $n$ 的序列有 $x$ 个 $1$，一个长度为 $m$ 的序列有 $m-x$ 个 $1$ 的方案数。 两个总共 $1$ 的个数一直是 $m$，对于任意一个长度为 $n+m$ 并且有 $m$ 个 $1$ 的序列分成左右两份即可得到原序列。 $$ ANS=\sum_{i=0}^n\binom{n}{i}\binom{m}{i}=\binom{n+m}{n}=\binom{n+m}{m} $$ 还可以直接套用范德蒙德卷积 $$ ANS=\sum_{i=0}^n\binom{n}{i}\binom{m}{i}=\sum_{i=0}^n\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m} $$ ## 2 > 有两个序列，一个序列长度为 $n$ 的序列，一个序列长度为 $m$，每个数均在 $[0,k]$ 中随机取一个整数，求两个序列的和相等的方案数。 令函数 $f(n,s)$ 表示一个长度为 $n$ 的序列，每个数取值为 $[0,k]$ 并且和为 $s$ 的方案数。 考虑用组合数计算不考虑每个数取值上限的方案数，再进行容斥，枚举有几个数超出。 $$ f(n,s)=\sum_{i=0}^{\left\lfloor\frac{s}{k}\right\rfloor}(-1)^{i}\binom{n}{i}\binom{s-ik+n-1}{n-1} $$ 设 $n<m$，枚举每个序列的和计算总方案数 $$ ANS=\sum_{i=0}^{nk}f(n,i)f(m,i) $$ 依然可以用特别恶心的卷积+生成函数。 考虑两个序列和为 $x$，把第二个序列中的每个数 $b_i$ 变成 $k-b_i$ 会得到唯一一个新序列。 现在的第二个序列的新序列每个数还是位于 $[0,k]$，总和变成了 $mk-x$。 把两个序列并在一起的序列满足总和为 $mk$，长度为 $n+m$ 对于任意一个总和为 $mk$ 的序列都可以分成左右两份，右边长度为 $m$ 的一份变化成唯一对应的原序列即可满足条件。 即为 $$ ANS=\sum_{i=0}^{nk}f(n,i)f(m,i)=f(n+m,mk)=f(n+m,nk) $$ Loading... ## 1 > 有两个序列，一个序列长度为 $n$ 的序列，一个序列长度为 $m$，每个数均在 $0,1$ 中随机取，求两个序列的和相等的方案数。 假设 $n<m$，可以列出最朴素的式子 $$ ANS=\sum_{i=0}^n\binom{n}{i}\binom{m}{i} $$ 若第一个序列有 $x$ 个 $1$ 和 $n-x$ 个 $0$，则第二个序列必须有 $x$ 个 $1$ 和 $m-x$ 个 $0$。 考虑对第二个序列进行反转，则第二个序列对应的新序列有 $m-x$ 个 $1$ 和 $x$ 个 $0$。 问题转化成一个长度为 $n$ 的序列有 $x$ 个 $1$，一个长度为 $m$ 的序列有 $m-x$ 个 $1$ 的方案数。 两个总共 $1$ 的个数一直是 $m$，对于任意一个长度为 $n+m$ 并且有 $m$ 个 $1$ 的序列分成左右两份即可得到原序列。 $$ ANS=\sum_{i=0}^n\binom{n}{i}\binom{m}{i}=\binom{n+m}{n}=\binom{n+m}{m} $$ 还可以直接套用范德蒙德卷积 $$ ANS=\sum_{i=0}^n\binom{n}{i}\binom{m}{i}=\sum_{i=0}^n\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m} $$ ## 2 > 有两个序列，一个序列长度为 $n$ 的序列，一个序列长度为 $m$，每个数均在 $[0,k]$ 中随机取一个整数，求两个序列的和相等的方案数。 令函数 $f(n,s)$ 表示一个长度为 $n$ 的序列，每个数取值为 $[0,k]$ 并且和为 $s$ 的方案数。 考虑用组合数计算不考虑每个数取值上限的方案数，再进行容斥，枚举有几个数超出。 $$ f(n,s)=\sum_{i=0}^{\left\lfloor\frac{s}{k}\right\rfloor}(-1)^{i}\binom{n}{i}\binom{s-ik+n-1}{n-1} $$ 设 $n<m$，枚举每个序列的和计算总方案数 $$ ANS=\sum_{i=0}^{nk}f(n,i)f(m,i) $$ 依然可以用特别恶心的卷积+生成函数。 考虑两个序列和为 $x$，把第二个序列中的每个数 $b_i$ 变成 $k-b_i$ 会得到唯一一个新序列。 现在的第二个序列的新序列每个数还是位于 $[0,k]$，总和变成了 $mk-x$。 把两个序列并在一起的序列满足总和为 $mk$，长度为 $n+m$ 对于任意一个总和为 $mk$ 的序列都可以分成左右两份，右边长度为 $m$ 的一份变化成唯一对应的原序列即可满足条件。 即为 $$ ANS=\sum_{i=0}^{nk}f(n,i)f(m,i)=f(n+m,mk)=f(n+m,nk) $$ 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏