数学杂谈总结 - “柳暗花明又一村”
2026-07-17 21:47:12
发布于：浙江
自主学习笔记类总结
——————————————————————————————————————————
今天学的东西还真挺多的。就用写掉的题目来做总结吧。
这是一道不能再模板的错位排序模板。
错位排序用到的知识：组合+容斥
#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;
}
错位排序基本公式：
但是我当时没有识别出这道模板题，遂大怒写了又一道模板题：https://www.luogu.com.cn/record/286701751
然后我又写了另一道容斥：https://www.luogu.com.cn/record/286687475 越狱
这道题目的思路是：由于我们很难直接求出相邻房间信仰相同的方案数
正难则反，考虑容斥。
所以们求出房间排列的所有方案，然后减掉房间信仰全部不同的数量。
在完成代码的时候，我遇到了一点小问题：
减法取模要记得+mod再取模。不然有概率变成负数。
然后我开始研究卡特兰数，先写掉了这题：https://www.luogu.com.cn/problem/P1044
栈
这道题是一个卡特兰数模板。
方便起见，我先写一下它的公式：
1.通项公式：
递推公式理解起来比较方便
但是由于涉及组合数有可能需要逆元，而有些题目会卡这个做法（就是把模数设定为一个合数，这样你就没办法用费马小定理）
比如这道题目：https://www.luogu.com.cn/problem/P1976
它的模数是，如果使用费马小定理就会坠机。
所以，我们要引出第二个公式：
2.递推公式：
它的理解实际上也不是特别难，可以像成一颗二叉树，你要枚举它的各种形态。
一共有个节点，根节点占据一个节点，假设它的左子树有个节点，那么它的右子树就会有个节点，然后的取值范围可以从到。
不过它需要注意以下初始化：
——————————————————————————————————————————
需要在后续完成的内容：
1.用容斥思想重新理解错位排序
2.写一点其他的容斥思想的题目
3.https://www.xinyoudui.com/ac/contest/747011277000BED0906435/problem/12279
写掉：牛牛的围栏
4.重新梳理卡特兰数两种公式的推到方式和理解方式
（重点关注为什么i从0到n-1，还有相乘的原因）
这里空空如也
有帮助，赞一个