题目大意
构造两个单调不减序列 \(a,b\)，满足下述条件：
-
两序列长度相等，设为 \(k\)
-
\(a_1=0,a_k=n,b_1=0,b_k=m\)
-
\(\forall i\in(1,k], a_{i-1}+b_{i-1}\neq a_i+b_i\)
求每个不同方案的 \(a\) 序列的长度总和
题解
不妨把问题由构造序列转化成网格图上走点
从 \((0,0)\) 走到 \((n,m)\) 的不同方案的经过的点的个数总和，且每次只能往右上走，不能不走
我们设 \(f(n,m)\) 为所求答案
直接去做感觉还是不太可做，考虑将二维问题去简化成一维的，即去求 \(f(n,0)\)
首先有 \(0\) 和 \(n\) 位置是一定会被选到的，然后剩下 \(n-1\) 个位置都有 \(\frac{1}{2}\) 的概率被选到，所以共有 \(2^{n-1}\) 种不同的方案
对于每一种方案，显然可以找到一个和他互补的方案，从而构成一个 \(n\) 个数都被选了的方案，这样显然只能构成 \(2^{n-2}\) 组
所以有
\[f(n,0)=2^{n-2}\times (\frac{n-1}{2}+1+1) \]然后我们把问题再拓展到二维，我们选出 \(k\) 个断点，这 \(k\) 个点必须选
我们将路径抽象化一个向上走一段，再向右走一段，依次轮换，然后这个长路径上的一些点可能不会被选到
断点的意义是向右一段到向上一段的拐点
选出 \(k\) 个断点的方案有 \(\binom{n}{k}\times\binom{m}{k}\)，然后把选出来的长路径化为一维上的点，即 \(n+m-k\) 个点选或不选，就是 \(f(n+m-k,0)\)，最后加上必选的 \(k\) 个断点的贡献 \(2^{n+m-k-1}\times k\)
所以最后答案即为
\[f(n,m)=\sum_{k=0}^{\min(n,m)}\binom{n}{k}\times \binom{m}{k}\times (f(n+m-k,0) + 2^{n+m-k-1}\times k) \] 标签：方案,Generation,选到,List,times,mathcal,binom,断点 From： https://www.cnblogs.com/Rubyonly233/p/16875375.html