初等数论杂谈2 - 向阳花

ToTheSun

2026-07-18 17:52:47

发布于：浙江

10阅读

0回复

0点赞

自学笔记类杂谈

又能隐隐约约深深浅浅地在黑夜中看到飘渺似无凭的向阳花 —— 庸人之夏

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

组合基础trick

$C_n^m=C(n,n-m)$
$C_n^m=C(n-1,m)+C(n-1,m-1)$ （从n个数中选出m个数，假设某一个数我没选，那么就要从剩下的n-1个数中选出m个数；假设某一个数我选了，那么就要从剩余的n-1个数中选出m-1个数）

很多组合数的基础公式和技巧都是可以用杨辉三角推出来的。（二项式定理， $2^n$ ，……）
组合数也经常被称为二项式系数。

还有一些二项式定理相关的（比如奇正偶负的情况下，杨辉三角一行加起来等于零。全正的情况下，加起来等于 $2^n$ ）关于它们的证明，都是可以直接有杨辉三角的模型一点点推/摸索出来的。

隔板法（插空法）

m这个数切割成n个数的和：在n-1个空位中，放m个板子
也就是 $C(n-1,m)$

m颗糖果分给n个小朋友（m分割成n个部分）

n个部分相加等于m

如何使用隔板法？确定序列 or 拆分序列 -> 隔板法

快速幂

这玩意儿我一万年前就见过了。但是至今其实不是特别理解。
https://www.luogu.com.cn/problem/P1226
所以现在来写一下思路好了。

我比较喜欢的做法是把 $b$ 二进制拆分掉： $a^{i_0}+a^{i_1}+....+a^{i_x}=a^b$
$b$ 可以拆分成一堆二的次幂相乘（详见二进制）
所以我们可以拥有这样一段代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll a,b,p;
	cin>>a>>b>>p;
	ll ans=1,a1=a;
	for(int i=0;i<=31;i++){
		if(b>>i&1)ans=(ans*a)%p;
		a=(a*a)%p;
	} 
	cout<<a1<<"^"<<b<<" mod "<<p<<"="<<ans;
	return 0;
}

来摸一个小例子，不然可能会有一点Bug。
样例：2 10 9
我们忽略mod
$10=2^3+2^1$
$2^{10}=2^{2^3}*2^{2^1}=2^8*2^2$
然后按照代码的形式去跑一遍整个过程：

$a=a*a=2*2=4=2^2$
$ans=ans*a=4$ & $a=a*a=4*4=2^2*2^2=2^4$
$a=a*a=2^4*2^4=2^8$
$ans=ans*a=2^2*2^8=2^{10}$

隔板法相关运用

https://www.luogu.com.cn/problem/P6475

这是一个很复杂的题目。

我们考虑将题目分段思考。
先抛弃“第x个数和第y个数相等”的部分。简单地思考“前n个数不下降”和“后n个数不上升”如何去计算有多少种方案。

考虑另一件事：其实我们可以把”不下降“也抛掉。因为我们可以直接考虑要在 $m$ 个数中选出 $n$ 个数的不同方案，假装它们后面会自己排序（而我们不需要考虑它的顺序）

而且注意到 $m$ 个数是可以重复选择的，那一共有多少种方法呢？

此时我们可以牵强地联系一下隔板法：比如我们有一个数列：[1,1,2,2,2,3]
那要放置的板就是：[1,1 | 2,2,2 | 3] 不过需要注意：我们不一定一定要在这个序列中塞上m个数（虽然我们有m个选择）

也就是说，我们接受空盒状态，那么总选择数就从 $C(n-1,m-1)$ 变成了 $C(n+m-1,m-1)$ （因为板和板也可以塞在一起）

n个位置的数不下降和不上升其实是相同的处理方式。因为顺序本身对组合来说并不重要。

所以接下来我们要考虑第x个数和第y个数相等的情况如何处理。
这里我们需要分类讨论。

1.第x个数和第y个数都在前n个数中
2.第x个数和第y个数都在后n个数中
3.第x个数和第y个数一个在前n个数里，一个在后n个数里

不难发现第一种情况和第二种情况是相似的。
所以我们打包解决。
（备注：高度是可以枚举的）

已知序列要求不下降。也就是说，从第x个数到第y个数必须全部相等。
此时序列分成三个部分：[1,x) [x,y] (y,n]
[x,y]是固定的，[1,x)和(y,n]可以重用大区间方案书的计算方法。毕竟通用。
（哦哦哦。这里需要注意的一个点是：需要把值域更改，因为理论上而言区间从左到有右拼接需要是有序的）
最后的方案书就是将前面区间的方案数乘上后面区间的方案数。

最后我们来看方案三。
我们需要考虑第x个位置为h，第y个位置为h的方案数。
这边将数值固定，也就是将x前后和y前后的区间的值域固定。

哦。也就是说，三种情况其实差不多。
只是最后一种方案需要重复两次操作。

终于把代码打完了。先把它放置在这里，然后我来逐行讲解。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
const int mod=998244353;
ll jc[N];
ll ans=0;
ll k(ll x,ll k){
	ll ans=1,xx=x;
	while(k){
		if(k&1)ans=(ans*xx)%mod;
		xx=(xx*xx)%mod;
		k>>=1;
	}
	return ans;
}
ll C(int n,int m){
	if(m<0||m>n)return 0;
	//*****)=n!/(m!*(n-m)!)
	return (jc[n]*k((jc[m]*jc[n-m])%mod,mod-2))%mod;
}
int main(){
	//预处理阶乘数组：
	jc[0]=1;
	for(ll i=1;i<N;i++){
		jc[i]=(jc[i-1]*i)%mod;
	}
	int m,n,x,y;
	cin>>m>>n>>x>>y;
	//楼的高度不能超过m，一共有2*n座高楼。
	//需要下标为x和下标为y的两栋楼高度相同 
	if(x>y)swap(x,y);
	if(x<=n&&y>n){
		ll ans=0;
		for(int h=1;h<=m;h++){
			//枚举高度
			//前面的高度值域是1-h，后面的高度值域是h-m 
			ll sum=(C(x+h-2,h-1)*C(n-x+m-h,m-h))%mod;
			sum=((sum*C(y-n+m-h-1,m-h))%mod*C(2*n-y+h-1,h-1))%mod;
			ans=(ans+sum)%mod;
		}
		cout<<ans;
		return 0;
	}
	if(x<=n&&y<=n){
		ll ans=0;
		for(int h=1;h<=m;h++){
			ll sum=(C(x+h-2,h-1)*C(n-y+m-h,m-h))%mod;
			sum=(sum*C(n+m-1,m-1))%mod;
			ans=(ans+sum)%mod;
		}
		cout<<ans;
		return 0;
	}
	if(x>n&&y>n){
		ll ans=0;
		for(int h=1;h<=m;h++){
			ll sum=(C(x-n+m-h-1,m-h)*C(2*n-y+h-1,h-1))%mod;
			sum=(sum*C(n+m-1,m-1))%mod;
			ans=(ans+sum)%mod;
		}
		cout<<ans;
	}
	return 0;
}

首先这道题目的各种边界很难调试。要调可能也只有瞪眼。
其次注意for循环二进制方法的快速幂如果边界设置不对可能会炸的你样例都过不去。
还有就是各种mod每一次乘法加法都要加mod，不然你也会挂分。

这道题确实有点吃操作。

矩阵

矩阵与矩阵的乘法：只有一个矩阵的列(n*m)和另一个矩阵的行(m *k)相同才可以相乘。6
则它们可以相乘并得到一个 $n*k$ 的矩阵C。

将方程问题转化成矩阵问题再解决。

快速幂2

我发现我的第一个版本快速幂会炸。
所以我打算再学一种新的！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p;
ll k(int x,int k){
	ll ans=1,xx=x;
	while(k){
		if(k&1)ans=(ans*xx)%p;
		xx=(xx*xx)%p;
		k>>=1;
	}
	return ans;
}
int main(){
	int a,b;
	cin>>a>>b>>p;
	cout<<a<<"^"<<b<<" mod "<<p<<"="<<k(a,b);
	return 0;
}