数学杂谈总结 - “柳暗花明又一村”

ToTheSun

2026-07-18 08:32:02

发布于：浙江

6阅读

0回复

0点赞

自主学习笔记类总结
——————————————————————————————————————————
今天学的东西还真挺多的。就用写掉的题目来做总结吧。

这是一道不能再模板的错位排序模板。

错位排序用到的知识：组合+容斥

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int mod=1e9+7;
ll f[N];
int main(){
	int n;
	cin>>n;
	f[1]=0,f[2]=1;
	for(int i=3;i<=n;i++){
		f[i]=((i-1)*(f[i-1]+f[i-2])%mod)%mod;
	}
	cout<<f[n];
	return 0;
}

错位排序基本公式： $f[i]=(i-1)*(f[i-1]+f[i-2])$

但是我当时没有识别出这道模板题，遂大怒写了又一道模板题：https://www.luogu.com.cn/record/286701751

然后我又写了另一道容斥：https://www.luogu.com.cn/record/286687475 越狱
这道题目的思路是：由于我们很难直接求出相邻房间信仰相同的方案数

正难则反，考虑容斥。
所以们求出房间排列的所有方案，然后减掉房间信仰全部不同的数量。

在完成代码的时候，我遇到了一点小问题：

减法取模要记得+mod再取模。不然有概率变成负数。

然后我开始研究卡特兰数，先写掉了这题：https://www.luogu.com.cn/problem/P1044
栈
这道题是一个卡特兰数模板。
方便起见，我先写一下它的公式：
1.通项公式： $C_n=C_{2n}^n-C_{2n}^{n-1}$
递推公式理解起来比较方便

但是由于涉及组合数有可能需要逆元，而有些题目会卡这个做法（就是把模数设定为一个合数，这样你就没办法用费马小定理）

比如这道题目：https://www.luogu.com.cn/problem/P1976
它的模数是 $1e8+7$ ，如果使用费马小定理就会坠机。

所以，我们要引出第二个公式：

2.递推公式： $C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}$
它的理解实际上也不是特别难，可以像成一颗二叉树，你要枚举它的各种形态。
一共有 $n$ 个节点，根节点占据一个节点，假设它的左子树有 $k$ 个节点，那么它的右子树就会有 $n-1-k$ 个节点，然后 $k$ 的取值范围可以从 $0$ 到 $n-1$ 。
不过它需要注意以下初始化： $C[0]=1$

——————————————————————————————————————————
需要在后续完成的内容：
1.用容斥思想重新理解错位排序
2.写一点其他的容斥思想的题目
3.https://www.xinyoudui.com/ac/contest/747011277000BED0906435/problem/12279
写掉：牛牛的围栏
4.重新梳理卡特兰数两种公式的推到方式和理解方式
（重点关注为什么i从0到n-1，还有相乘的原因）
——————————————————————————————————————————
1.用容斥思想重新理解错位排序

虽有排列的总是（全排列）是 $n!$ ，但是直接思考“有一个元素在自己的位置上”的情况很复杂。