数论杂谈 - “人生若只如初见。”

Baltic 菠萝的海

2026-07-17 21:19:57

发布于：浙江

15阅读

0回复

0点赞

自主学习笔记类产物
——————————————————————————————————————————

mod相关，同余问题（同余最短路之类的）

1.把其他问题转化成同余问题
2.作为题目的一部分（取模）
3.NOIP：中国剩余定理

组合数学 ->DP

1.容易在S组考

线性代数 ->优化算法

1.可能在NOIP有30pts左右的部分分

基本计数原理

加法原理，乘法原理

加法原理

加法原理适用于互不相交的事件。
如果事件A和事件B互不相交，那么A和B发生的总数是A+B

乘法原理

推广为两个以上的事件，如果各个事件之间相互独立，同时发生的方案事就为各个时间方案数的乘积

排列数与组合数

$A_n^m$ （考虑顺序） $=\frac{n!}{(n-m)!}=(n-m+1)!$
$C_n^m$ （不考虑顺序） $=\frac{n!}{m!(n-m)!}=\frac{(n-m+1)!}{m!}$

容斥原理

图->式子

容斥原理在二维矩阵中的运用：二位前缀和

生成函数L如果不想用递推买也可以用生成函数。

1.有多少种方案数能够构成最大价值
2.输出每种方案

这两个要求无法在多项式复杂度内完成（1.无后效性 2.方案数量很大（输出不完））
计算方案数大概用的是二维动态规划

计数动态规划只是继承（通常）

最短路记数
https://www.luogu.com.cn/problem/P1144

代码不太想打，核心其实只是这两行式子，剩下的都是模板：

$dis[u]+w(u,v)==dis[u,v]$ $f[v]+=f[u]$
$dis[u]+w(u,v)<dis[u,v]$ $f[u]=f[v]$

想了想，还是打算趁着课间打一下代码。
过程还行，有个地方卡了一下，最后发现是重载运算符写错了。太久不写了喵。
把代码放置一下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
struct Node{
	int z,q;
	friend bool operator < (Node a,Node b){
		return a.q>b.q;
	}
};
vector<Node>v[N];
priority_queue<Node>pq;
int dis[N],l[N];
bool vis[N];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back({y,1});
		v[y].push_back({x,1});
	}
	pq.push({1,0});
	for(int i=0;i<=n+1;i++)dis[i]=INT_MAX;
	dis[1]=0;
	l[1]=1;
	while(!pq.empty()){
		Node sum=pq.top();
		pq.pop();
		int k=sum.z;
        if(vis[k])continue;
		vis[k]=1;
		for(int i=0;i<v[k].size();i++){
			int to=v[k][i].z;
			int len=v[k][i].q;
			if(dis[to]>dis[k]+len){
				l[to]=l[k];
				dis[to]=dis[k]+len;
				pq.push({to,dis[to]});
			}else if(dis[to]==dis[k]+len){
				l[to]=(l[to]+l[k])%100003;
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<l[i]<<'\n';
	}
	return 0;
}

容斥与排列组合的关联：
正难则反。容斥在我这里会更偏向于一种思想而不是一种方法。
如果你正着去推一种排列组合，很难推。那你可以先把所有的情况全部都推出来（一般是全排列）
然后把与你想求的那些东西恰好相反的情况减掉。（这就是一种容斥原理）

生成函数

普通生成函数：与顺序无关
指数生成函数：与顺序有关

它们会由原来的一个递推式去不断地花间形成，看起来很简单，但是其实你不一定推理到你想要的式子。

——————————————————————————————————————————
上午的课程已经上完了，但其实我还不够了解，所以先弄道题目练练手。
https://www.luogu.com.cn/problem/P7149
奶牛围栏

题目大意：一些点分散在坐标系中，寻问有多少种在坐标系中画一个矩形且不同矩形内的点集不同的方式。

第一道与组合计数或者容斥相关的题，几乎没有思路。所以找deepseek搭了几个板子：

一. 把“矩形”翻译成“选点”
一个矩形的关键是它围住了哪些点，且一个矩形是由最上，最下，最左，最右的点决定的

二. 思考计数策略
枚举矩形的某一条边界，计算由这条边界决定的矩形数量
比较容易想到（？）枚举矩形的左右边界，而后将问题转化为：在这块区域中，有多少种选择上下边界的方式，使得它们形成一个合法的矩形（合法的定义，取决于如何避免重复计数）

三.如何避免重复计数？

如果直接枚举所有可能，一定会重复计数。为了避免重复，对于每一个可以被矩形围起来的点集，我们要为它找到一个唯一的“代表矩形”。
一个经典的技巧是：强制要求矩形的上下边界都刚好紧贴着某个点。
在固定左右边界后，我们就可以枚举上下边界所在的行。

然后在思考过程中，我发现了一个比较麻烦的点：

通常情况下，我熟悉的是x行y列&格子，但是这边由于是在坐标系中，它变成了：y行x列&点。
所以，需要梳理一下两者之间的不同。

核心思路：枚举矩阵 -> 枚举举行对角线（而不是上下左右）（左上右下or右下左上）->如何维护不同奶牛子集数量？->右下点往下/往右扩展，会添加什么？

卡特兰数

是组合书中极其重要的数列。

括号匹配：右括号数量一定不能大于左括号数量
求n个节点构成的不同形态的二叉树数量

各种数列都应该将前几位（10？）背下来，这样在考场上，你先写了几个dp的式子的答案。直接对出了是xxx数列，然后你就可以将递推式（超时）变为O(1)直接出的生成函数（阶乘预处理）

——————————————————————————————————————————

逻辑梳理

今天讲的东西看起来很散，其实是有内部逻辑的。让我们来梳理一下。

一个核心问题：给定一堆东西，询问有多少种安排方式。

排列

东西是不同的，怎么排？

排序是一切的根源。 $A_n^m=(n-m+1)!$

组合

东西是不同的，但是我不关心顺序，怎么组？
$C_n^m$ 只要在 $A_n^m$ 的基础上去掉 $m$ 的顺序，也就是除以 $m!$ （ $m$ 的全排列）

容斥

上文中我已经提到过，容斥思想是可以与组合关联的，也就是正难则反思想的一种体现。
合法量=总量-非法量

卡特兰数

——————————————————————————————————————————

练习

练习是必不可少的。
https://www.luogu.com.cn/problem/P3197 越狱
这道题就是容斥原理的一种（比较典）的运用。
不难发现如果想要求出宗教们凑在一起的方案数是一件比较困难的事情。

所以我们可以尝试：先算出所有排列的情况，然后把宗教们不凑在一起的情况减掉。
那一共有多少种情况呢？
$m^n-m(m-1)^{n-1}$

注意到可能需要快速幂。
放置一下代码，然后提一下容易WA的地方：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=100003;
ll pow1(ll a,ll b){
	ll aa=a,ans=1;
	for(int i=0;i<=60;i++){
		if(b>>i&1)ans=(ans*aa)%mod;
		aa=(aa*aa)%mod;
	}
	return ans;
}
int main(){
	ll m,n;
	cin>>m>>n;
	//m^n-m(m-1)^{n-1}
	cout<<(pow1(m,n)-(m*pow1(m-1,n-1))%mod+mod)%mod;
	return 0;
}

(pow1(m,n)-(m*pow1(m-1,n-1))%mod+mod)%mod

减法取模容易炸成负数，所以记得要(a-b+mod)%mod

https://www.luogu.com.cn/problem/P1595
信封问题，小板板，可爱捏。

错位排列

这玩意儿在我眼里其实和卡特兰数差不多，反正都是为一个专门的问题准备的一个专门的答案。
区别是错位排列相当简单，卡特兰数我没有听懂。
一个递推式总结：
$f[i]=(i-1)*(f[i-1]+f[i-2])$

原理：
考虑有一个长度为i的数列，现在你在填它的最后一位，励志将它填成错位排列。

1.它前面的i-1位都是错位排列，只是后我们将第i位数字与这i-1个数字中的随机一个交换，都可以构成新的错位排列。此时我们一共有 $(i-1)*f[i-1]$ 种选择
2.它前面的i-1位有i-2位都是错位排列，此时我们将那1位不是错位排列的数字与i交换，可以构成新的错位排列，此时我们一共有 $(i-1)*f[i-2]$ 种选择