错排问题
令 \(dp[i]\) 表示一个 \(i\) 的排列的方案数。
考虑当前插入一个数 \(i\), 那么考虑一个位置 \(pos\)，显然 \(pos\) 有 \(i - 1\) 种选择
-
假设 \(i\) 放在了 \(pos\) 位，那么相当于剩下的 \(i - 2\) 个数错排
-
假设不放在 \(pos\) 位，那么相当于有另一个 \(pos\) 被占位，放了 \(i\) 但是剩下了 \(i - 1\) 个位置和 \(i - 1\) 个数，所以相当于 \(i - 1\) 个数错排。
综上 \(dp[i] = (i - 1) \times (dp[i-1] + dp[i-2])\)
传球游戏
挺水的...
令 \(dp[i][j]\) 表示第 \(i\) 个人在 \(j\) 轮后回到自己手中的方案，那么显然有转移 \(dp[i][j] = dp[left(i)][j-1] + dp[right(i)][j-1]\)
边界条件是 \(dp[1][0] = 1\)。
数的划分
乍一看是不是很像组合数学，其实不然，这里方案的排列算同一种。
同样的令 \(dp[i][k]\) 表示数 \(i\) 分成 \(k\) 段的方案数。
先观察边界，发现有
- \(k = 0\) 则 \(dp[i][k] = 0\)
- \(k > i\) 则 \(dp[i][k] = 0\)
- \(k = i\) 则 \(dp[i][k] = 1\)
想想怎么理解这个递推，假设我们现在有了 \(k\) 段，那么每段必然大于 \(0\)。那么其实你可以玩一个文字游戏：这些段的种类分为
- 至少包含一份 \(1\) 的，对应着 \(dp[i-1][k-1]\)
- 不包含 \(1\) 的，那么每一段都大于 \(1\),那么方案其实就是 \(dp[i-k][k]\),代表将每一份都扣掉 \(1\)。
总转移:\(dp[i][k] = dp[i-1][k-1] + dp[i-k][k]\)
栈的问题
好经典的卡特兰数！且听我细细道来。
这里讲两种做法，一种是递推做法，一种是组合数学的做法。
递推
我们令 \(dp[i]\) 表示前 \(i\) 个数的出栈序列的方案数。
想这样一个问题，假设我当前一个长度为 \(i\) 的序列全部从原序列中出来了，那么现在分成两类：在栈中的，已经过去固定了的。
考虑栈底元素，记为 \(k\)，那么显然 \(k\) 有 \(i\) 种取值，且有不在栈中已经固定的必定比 \(k\) 小，在栈中的必定比 \(k\) 大，那么这两部分的答案分别为 \(dp[k-1]\) 和 \(dp[n-k]\) 二者之间为分步乘法原理，所以总的递推就是 \(dp[i] = dp[0] \times dp[i-1] + dp[1] \times dp[i-2] + .... + dp[i-1] \times dp[0] (i \ge 2)\)。
组合
这其实是一个经典的折线计数法。
我们将一个数压入栈中看成对栈内元素个数的 \(+1\) 操作，将一个数弹栈看成栈内元素个数的 \(-1\) 操作，那么问题就变成了：
- \(n\) 次 \(+1\) 操作
- \(n\) 次 \(-1\) 操作
且栈内元素个数始终非负
的方案数。
这个问题可以从二维来看，也可以从一维来看。
二维平面角度：
横坐标为 \(+1\) 个数，纵坐标为 \(-1\) 个数。
那么原问题等价于：从 \((0,0)\) 走到 \((n,n)\) 且不触碰 \(y = x + 1\) 这条直线的步数，因为如果触碰那么 \(x - y = -1\) 栈内元素个数为负数。
那么这个方案数 = 总方案数 - 碰到 \(y = x + 1\) 的方案数。
总方案数为 ： \(\binom{2n}{n}\) 代表着从 \(2n\) 步里选出 \(n\) 步走 \(+1\) 的方案数。
碰到的方案数为： \(\binom{2n}{n-1}\) 组合意义同理，其实就是将 \((n,n)\) 关于 \(y = x + 1\) 对称了一下得到 \((n-1,n+1)\) 因为到这条直线的方案数，一定会过 \(y = x + 1\)。
所以答案就是 \(\binom{2n}{n} - \binom{2n}{n-1}\) 化简一下就是 \(\frac{\binom{2n}{n}}{n+1}\)。
一维数轴角度
从原点出发，走 \(n\) 步 \(+1\) 和 \(n\) 步 \(-1\) 最后回到原点且中间不到达负半轴的方案数。
那么其实思想就和上面二维的一样了。
将原点关于 \(-1\) 对称一下，得到 \(-2\) 这个点，然后解一下方程：
\(x + y = 2n\)
\(x - y = -2\)
解得 \(x = n - 1,y = n + 1\) 你会发现和二维的一样了，所以公式也都一样了。
一不小心讲多了。
划分数列
\(dp[i][0/1]\) 表示到 \(i\) 为 \(0升/ 1降\) 的方案数。
然后就分类讨论一下就好了..
f 函数
预处理一下就好了,先大的，再小的。
无限序列
手玩一下，发现就是个斐波那契数列，第 \(i\) 次操作的 = 第 \(i-1\) 次操作的 + 第 \(i-2\) 次操作的。
所以预处理一下，变为前缀和相减的形式
#define int long long
const int N = 100;
int q, a, b;
int f[N], s[N];
int get(int x) {
rep(i, 0, 90) {
if (s[i] == x)
return f[i];
else if (s[i] > x)
return f[i - 1] + get(x - s[i - 1]);
}
return 0;
}
signed main() {
f[1] = f[2] = 1;
s[1] = 1;
s[2] = 2;
rep(i, 3, 90) f[i] = f[i - 1] + f[i - 2], s[i] = s[i - 1] + s[i - 2];
read(q);
while (q--) {
read(a, b);
printf("%lld\n", get(b) - get(a - 1));
}
}
序列个数
这题很强悍！
考虑一个 \(n \times n\) d 矩阵，\((i,j)\) 表示在第 \(i\) 个位置放 \(j\), 那么对于 \(a[i]\)，符合答案的就是在 \(i \times i\) 的子矩阵里恰好有 \(a[i]\) 个点。
那么分类讨论：
-
$a[i] = a[i-1] $ 答案不变。
-
\(a[i] = a[i-1] + 1\) 那么在当前的 \(i\times i\) 的矩阵里扣掉 \((i-1) \times (i-1)\) 的矩阵，还剩下 \(i * 2 - 1\) 个位置，但是还要扣掉之前的 \(2 \times a[i-1]\) 个位置。所以 \(ans *= (i * 2 - 1 - 2 * a[i-1])\)。
-
\(a[i] = a[i-1] + 2\) 对于扣掉后剩下的大 L 显然横竖两部分独立，且对角线不填，那么每一部分都是 \((i - 1 - a[i-1])\) 个位置，乘法原理，\(ans *= (i - 1 - a[i-1]) ^2\)
-
\(a[i] \ge a[i-1] + 3\) 每行每列最多一个，显然无解。
等距跳跃
额，不会dp做法，但是暴力跑的飞快，枚举点，斜率，暴力跳就做完了qwq，似乎卡不掉这样做法。
标签：方案,那么,YBTOJ,个数,times,dp,2n,合集,递推 From： https://www.cnblogs.com/wsxxs/p/16623906.html