数学相关学习笔记
1. 斯特林数
1.1. 第二类斯特林数
表示将 n 个互不相同的元素划分成 k 个集合的方案数。
\(S(n,k)=S(n-1,k-1)+kS(n-1,k)\)
因为对于一个新数，考虑它的放入情况，首先是可以单开一个集合，方案数 \(S(n-1,k-1)\)。
其次是放入任意一个集合，因为集合之间的数相互区分，所以集合之间相互区分，共 \(kS(n-1,k)\) 种。
边界是 \(S(n,0)=[n=0]\)
考虑容斥原理，将 n 个元素放入 i 个两两不同的集合，允许空集，方案数 \(i^n\)，记为 \(g(i)\)。
如果不允许有空集，方案数记为 \(f(i)\)，有 \(g(i)=\sum_{j=0}^i C_i^j f(i)\)
根据二项式反演 \(f(i)=\sum_{j=0}^i (-1)^{i-j}C_i^j g(j)=\sum_{j=0}^i (-1)^{i-j}C_i^j j^n=\sum_{j=0}^i \dfrac{(-1)^{i-j}i!j^n}{j!(i-j)!}\)
因为斯特林数的集合互不区分，所以还要除去集合的排列数：
\(S(n,m)=\sum_{i=0}^m \dfrac{(-1)^{m-i}i^n}{i!(m-i)!}\)
同一行第二类斯特林数计算
同一行表示元素个数相同，但是有不同的集合数量，求出所有数。
观察上面的式子，设 \(f(i)=\frac{i^n}{i!},g(i)=\frac{(-1)^i}{i!}\) 然后就是卷积了。
点击查看代码
#include<cstdio>
#define ll long long
using namespace std;
const int N=2e5+5,mod=167772161,g=3,invg=55924054;
int n;
ll inv[N],fac[N],a[N*3],b[N*3];
ll qpow(ll x,int y)
{
ll res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
void NTT(ll *a,int n,int opt)
{
if(n==1) return ;
int m=n/2;
ll p1[m],p2[m];
for(int i=0;i<m;i++) p1[i]=a[i*2],p2[i]=a[i*2+1];
NTT(p1,m,opt),NTT(p2,m,opt);
ll w=qpow(opt==1?g:invg,(mod-1)/n),wk=1;
for(int i=0;i<m;i++,wk=wk*w%mod)
{
a[i]=(p1[i]+wk*p2[i])%mod;
a[i+m]=(p1[i]-wk*p2[i])%mod;
}
}
int main()
{
scanf("%d",&n);
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++)
{
fac[i]=fac[i-1]*i%mod;
inv[i]=qpow(fac[i],mod-2);
}
for(int i=0;i<=n;i++)
{
a[i]=qpow(i,n)*inv[i]%mod,b[i]=(i%2?-1:1)*inv[i];
}
int len=1;
while(len<=2*n) len*=2;
NTT(a,len,1),NTT(b,len,1);
for(int i=0;i<len;i++) a[i]=a[i]*b[i]%mod;
NTT(a,len,-1);
ll p=qpow(len,mod-2);
for(int i=0;i<=n;i++)
{
printf("%lld ",(a[i]*p%mod+mod)%mod);
}
return 0;
}
同一列要指数型生成函数，不会。
1.2. 第一类斯特林数
n 个不同的数，划分成 k 个不同的非空轮换集合，集合之间不做区分的方案数。
递推式：\(s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)\)
\(s(n-1,k-1)\) 表示单开一个集合，\((n-1)s(n-1,k)\) 表示放到任意一个数后面。
1.3. 常用公式
\(x^n=\sum_{i=0}^n S(n,i) x^{\underline{i}}=\sum_{i=0}^nC_x^i i!S(n,i)\)
\(C_n^m m^{\underline{k}}=C_{n-k}^{m-k} n^{\underline{k}}\)
\(x^{\underline{n}}=\sum_{i=0}^n s(n,i) (-1)^{n-i} x^i\)
\(x^{\overline{n}}=\sum_{i=0}^n s(n,i) x^i\)
根据上面的东西可以得到斯特林反演的式子：
已知 \(g(n)=\sum_{k=0}^n (-1)^{n-k} s(n,k) f(k)\)
可以得到：\(f(n)=\sum_{k=0}^n S(n,k) g(k)\)
1.4. 例题
[省选联考 2020 A 卷] 组合数问题
首先根据 \(x^n=\sum_{i=0}^n S(n,i) x^{\underline{i}}\) 将普通多项式转成下降幂，记为 \(f(x)=\sum b_ix^{\underline{i}}\)。
然后就是推式子：
[集训队互测 2011] Crash 的文明世界
因为 \(x^n=\sum_{i=0}^nC_x^i i!S(n,i)\)，所以可以转成对每个 \(i\le k\) 求每条到 u 路径上选 i 条边的方案数。
因为 \(n\le 5\times 10^4\) 所以换根一下。
[HEOI2016/TJOI2016] 求和
先把除去斯特林数的部分提出来变成 \(\sum_{j=1}^n 2^j j!\sum_{i=1}^n S(i,j)\)
然后直接带通项公式 \(\sum_{j=1}^n 2^j j!\sum_{i=1}^n \sum_{k=1}^i\dfrac{(-1)^k(j-k)^i}{k!(j-k)!}\)
然后交换求和顺序：\(\sum_{j=1}^n 2^j j! \sum_{k=1}^i \dfrac{(-1)^k\sum_{i=1}^n(j-k)^i}{k!(j-k)!}\)
等比数列求和，后面的就可以大力 FFT 设 \(f(i)=\frac{(-1)^i}{i!},g(i)=\frac{i^{n+1}-1}{(i-1)i!}\)
5093: 图的价值
显然拆到每个点上算贡献，因为点之间互不影响，所以直接乘 n。
考虑到不与当前点相连的边可以随便选，所以贡献再乘上 \(2^{\frac{(n-1)(n-2)}{2}}\)
然后就是这个东西 \(\sum_{i=0}^{n-1} C_{n-1}^i i^k\)
根据 \(x^n=\sum_{i=0}^n S(n,i) x^{\underline{i}}\)，再交换一下求和顺序，得到：
\(\sum_{j=1}^k S(k,i)\sum_{i=1}^n C_{n-1}^i i^{\underline{j}}\)
然后得到 $\sum_{j=1}^k S(k,i) n^{\underline{j}} \sum_{i=1}^n C_{n-1-j}^{i-j} $
后面那东西就是 \(2^{n-j-1}\)，FFT求一下斯特林数即可。
[FJOI2016] 建筑师
这个比较神秘，看到只会想 dp T^T。
可以发现最高的一定是放在哪里都能看见的，考虑划分剩下的部分。
将这 n-1 个数划分成 \(a+b-2\) 组，然后让最高的放在左/右端点，这样将这些组依次拼接，组个数就是从一侧能看到的个数。
因为已经从中间划开，所以两边不互相影响，从划出的组里面选出 \(a-1\) 个排好序放左边，剩下排序后放右边。
关于如何分组，直接固定显然是不好做的，考虑到因为最大值的位置确定，把每个集合看成环，就是划好后把最大值转到对应位置。
所以这部分就是第一类斯特林数。
异或图
设 \(f(i)\) 表示钦定 i 个块两两不连通，\(g(i)\) 表示恰好，所以存在：
\(f(i)=\sum_{k=i}^n S(k,i) g(k)\)
根据斯特林反演可以得到：\(g(i)=\sum_{k=i}^n (-1)^{k-i} s(k,i) f(k)\)
考虑如何求 \(f(k)\)，考虑把这些数划分成若干个集合，然后就能找到有限制的边，即要求异或值为 0。
这个类似于高斯消元，把这些边的状态拉出来，就是一个数，要求选一些数，异或最终值为 0。
有一个东西叫线性基，可以依次把数插进去，这样一个数能被线性基里的数表示，那么随便选。
求划分的情况就是 \(Bell(n)\)，这个可以 dfs。
2. 二项式反演
2.1. 概述
设 \(f(i)\) 表示恰好选 i 个数组成特定结构的方案数， \(g(i)\) 表示从 i 中选出任意个元素组成特定结构的方案数，则有:
\(g(n)=\sum_{i=0}^n C_n^i f(i)\)
如果已知 \(g(i)\)，求 \(f(i)\)，有如下公式： \(f(n)=\sum_{i=0}^n (-1)^{n-i}C_n^i g(i)\)
证明：
将 \(g(i)\) 展开得到：
然后交换求和顺序，就能把 \(f(j)\) 提出去，得到：
因为 \(C_n^m C_m^k=C_n^k C_{n-k}^{m-k}\)，这个式子考虑组合意义，相当于 n 个数选出两个集合，一个大小为 k，一个大小为 m-k，这是两种不同的求法。
根据这个式子得到：
令 k=i-j 则：\(f(n)=\sum_{j=0}^n C_n^j f(j) \sum_{k=0}^{n-j} C_{n-j}^{k} (-1)^{n-k-j}\)。
有公式 \(\sum_{i=0}^n (-1)^i C{n}^i=[n=0]\) ，n=0 只有 \(C_0^0=1\) 必然成立。
考虑递推公式 \(C_i^j=C_{i-1}^j+C_{i-1}^{j-1}\)，看上一行对这一行的贡献形式。
显然每个数会贡献到 \(C_{i+1}^j,C_{i+1}^{j+1}\) 必然一奇一偶，所以结论成立。
根据这个得到：\(f(n) =\sum_{j=0}^n C_n^j f(j) [n=j]=f(n)\)。
同时还有一个相对常用的东西，记 \(g(i)\) 表示至少 i 个，f 不变。
有 \(g(n)=\sum_{i=k}^n C_i^n f(i)\)。
用上面类似的东西去推得到 \(f(k)=\sum_{i=k}^n (-1)^{i-k} C_i^k g_i\)
2.2. 例题
小w的喜糖
其实一开始的东西是对的，但是犯蠢没清空……
设 \(f_i\) 表示至多有 i 个是满足不相同条件的方案数。
考虑一下这东西是怎么构成的，就是先选 i 个数出来然后求排列，但是数字可重复。
考虑背包，转移方程是 \(f_i=\sum_{j=0}^{cnt} f_{i-j} C_{cnt}^j C_{i}^j\)。
然后直接代二项式反演的式子就结束了。
已经没有什么好害怕的了
第一行记为 a，第二行记为 b。
首先知道 n，k，容易求出有多少个满足 \(b>a\)。
设 \(f_i\) 表示至少有 i 对满足 \(b>a\)，那么外面的部分就是一个排列，考虑配对中的部分。
先对两个序列分别排序，对于每个 \(b_i\) 求出 a 中有多少小于它，记为 \(p_i\)。
从前往后做背包，那么如果当前这个匹配，贡献就是 \(f_j=f_{j-1}*(p_i-j+1)\)
直接代二项式反演公式即可。
3. min-max 容斥
3.1. 公式
对于集合 \(S\)，存在等式：
\(\max(S)=\sum_{T\in S} (-1)^{|T|-1} \min(T)\)
\(\min(S)=\sum_{T\in S} (-1)^{|T|-1} \max(T)\)
证明：
设集合 \(S=\{s_1,s_2,\dots,s_n\}\) 满足 \(\forall i<j s_i>s_j\)。
考虑 \(\min(T)=s_k\) 的情况：
若 \(k=1\) 那么只能选一个数，结果为 \((-1)^0 s_1=s_1\)。
若 \(k>1\)，前面系数的值就是 \(\sum_{i=0}^{k-1} (-1)^i C_{k-1}^i\) 就是 0，相加等式成立。
记 \(\max_k(S)\) 表示 S 的第 k 大值，扩展一下，有公式：
\(\max_k(S)=\sum_{T\in S} (-1)^{|T|-k} C{|T|-1}^{k-1} \min(T)\)
\(\min_k(S)=\sum_{T\in S} (-1)^{|T|-k} C{|T|-1}^{k-1} \max(T)\)
证明方法同上，把 \(C{|T|-1}^{k-1}\) 当系数直接提出来就行了。
还有一个期望式：
\(E(max(S))=\sum_{T\in S} (-1)^{|T|-1} E(\min(T))\)
gcd-lcm 容斥：
\(lcm(S)=\prod_{T\in S} gcd(T)^{(-1)^{|T|-1}}\)
放到次数上，那么 lcm 相当于取 max，gcd 相当于取 min。
乘法是加，除法是减，那么把每个因子拆开就是 min-max 容斥。
3.2. 例题
最小公倍佩尔数
这题实在有点神秘。
先考虑怎么求 f，公式是 \(f_i=2f_{i-1}+f_{i-2}\)。
考虑 g 的问题，有一个结论 \(f_{n+m}=f_{n+1}f_{m}+f_nf_{m-1}\)。
证明的话，根据上面的东西容易写出矩阵，看作矩乘去组合就行了。
然后因为 \(gcd(2,1)=1,gcd(f_1,f_2)=1\) 所以 \(gcd(f_i,f_{i+1})=1\)。
做一下辗转相除得到 \(gcd(f_{n+m},f_n)=gcd(f_{n},f_{m})=f_{gcd(n,m)}\)。
然后做就是 lcm-gcd 容斥，得到 \(g_i=\prod f(gcd(T))^{(-1)^{|T|}-1}=\prod_{i=1}^n f_i^{\sum [gcd(T)=i](-1)^{|T|-1}}\)。
考虑上面这部分怎么处理，记 \(a_i=\sum [gcd(T)=i](-1)^{|T|-1},A_i=\sum_{i|d} a_d\)。
然后因为没有空集，可以发现 \(A_i=1\)，莫反带回去是 \(a_i=\sum_{i|d} \mu(\frac{d}{i}) A_d\)。
换一下求和顺序得到 \(\prod_{i=1}^n \prod_{d|i} f(d)^{\mu{\frac{i}{d}}}\)
[HAOI2015] 按位或
出现时间类问题，全部出现不好求，但是第一个是好求的，而第一个相当于 min，全出现相当于 max，所以可以 min-max 容斥。
然后考虑怎么求 min，其实就是对于一个集合，看选中包含集合中任意一个点的数被选中的期望次数。
这部分可以随便 \(O(3^n)\)。
正难则反，考虑不在这些集合中的数字的概率，然后相减，使用高维前缀和可以 \(O(n2^n)\)
4. 辛普森积分法
4.1. 定积分基础知识
可以看作就是求一个函数在一段区间内的面积。
假设所求区间为 \([a,b]\)，在中间插入 n 个点满足 \(a=x_1<x_2<\dots<x_n=b\)，然后取一些点记为 \(\xi_i \in [x_i,x_{i+1}]\)，令 \(\Delta x_i=x_{i+1}-x_i\)，然后求出函数值，贡献为 \(\Delta x_i f(\xi_i)\)。
最终答案为 \(\sum_{i=1}^{n-1} \Delta x_i f(\xi_i)\)，这东西叫黎曼和。
可以发现 x 取得越密，值就越接近实际值，最终会趋近于一个极限为 \(I\)，称 \(I\) 为 \(f(x)\) 在区间 \([a,b]\) 上的定积分，记为 \(\int_a^b f(x) dx\)。
其中 \(f(x)\) 表示被积函数，\(f(x)dx\) 表示被积表达式，x 叫被积变量，a,b分别是上下界。
定义：
\(\int_a^a f(x) dx=0,\int_b^af(x) dx=-\int_a^b f(x) dx\)
可以发现有如下性质：
-
线性性：\(\int_a^b (f(x)+g(x))dx=\int_a^b (f(x))dx+\int_a^b (g(x))dx\)
-
对区间有可加性 \(\int_a^b (f(x))dx+\int_b^c (f(x))dx=\int_a^c (f(x))dx\)
-
保号性，对于区间 \([a,b]\)，如果满足区间内 \(f(x)>0\) 则 \(\int_a^b\)
牛顿-莱布尼茨公式：对于函数 \(f(x)\) 和 \(F(x)\)，若满足 \(F'(x)=f(x)\)，则存在：
所以对于任意函数，如果知道它的原函数，就能求出积分值。
4.2. 自适应辛普森积分法
如果给定了一个奇怪的函数，可以用一个图像与它近似的初等函数图像来代替，这个过程称之为拟合。
对于一个二次函数，它在 \([l,r]\) 区间内的积分大约值为 \((f(l)+f(r)+4f(mid))*(r-l)/6\)，不证了。
所以我们考虑将函数分成若干段，然后对每一段拟合一个二次函数，然后把这个东西当作这一段的积分值。
但是这么做有一个非常严重的问题，就是如果段数太少，就会误差过大，算出来什么都是合理的，段数太多时间复杂度爆炸。
考虑二分，但是这里的二分不是找答案，而是划分区间，对每个区间去拟合。
但是二分的终止条件变为函数图像足够相似，关于如何判断相似，可以直接和左右区间分别拟合的结果比较，差在一定范围内即为相似。
4.3. 例题
【模板】自适应辛普森法 1
按照上面的弄就行了
#include<cstdio>
#include<cmath>
using namespace std;
double a,b,c,d,l,r;
double f(double x)
{
return (c*x+d)/(a*x+b);
}
double get(double l,double r)
{
double mid=(l+r)/2.0;
return (f(l)+4.0*f(mid)+f(r))*(r-l)/6;
}
double solve(double l,double r)
{
double mid=(l+r)/2.0;
double v1=get(l,r),v2=get(l,mid)+get(mid,r);
if(fabs(v1-v2)<1e-10) return v2;
return solve(l,mid)+solve(mid,r);
}
int main()
{
scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&l,&r);
printf("%.6lf",solve(l,r));
return 0;
}
[CQOI2005] 三角形面积并
可以构造一个函数，\(f(x)\) 表示这些三角形与 x 条线的相交的长度。
那么函数图像下面的面积就是答案，直接上普通积分不行，因为比如有一些很小的就不会被统计上，所以要设定一个层数。
[NOI2005] 月下柠檬树
几何题，先说结论，圆投影下来还是圆，圆心位置就是高度乘上 \(cot(alpha)\)，不会证。
其余部分就是相邻圆的切线，从中间劈开，可以发现就是计算一个函数图像到 x 轴的面积，可以积分。
考虑如何计算每个点的长度，分成两部分：
- 圆上的弦
因为知道当前查询的 x 坐标，即 EF，知道半径，可以勾股。
- 切线
这里的切线是两个圆之间的切线，考虑怎么求交点。
先从圆心向切点连线 AE,CD，然后切点向横轴做垂 EH,FI，作 \(AG\bot CF\)。
那么 \(AGFE\) 为长方形，所以 \(GF=AE=r1\)，所以 \(CG=r1-r2\)。
所以可以勾股得到 AG，可以发现有个一线三垂直模型，还有对顶角相等，所以 \(\Delta AHE,\Delta AGC,\Delta CFI\) 相似，就能算坐标了。
接下来就是辛普森积分。
5. min_25 筛
5.1. 算法过程
直接从模版出发：【模板】Min_25 筛
先按照是不是质数分开求和，得到：
考虑枚举每个数的最小因子，然后得到：
但是 n 实在太大了，所以没有办法线筛求质数，考虑 dp。
设 \(g(n,i)\) 满足 \(g(n,j)=\sum_{i=1}^n [i\in p| minp > p_j]f'(i)\)
注意，这里的 \(f'(i)\) 是在质数位置和 \(f(i)\) 一样的完全积性函数。
考虑 \(g(n,j)-g(n,j-1)\) 若 \(p_j^2>n\) 那么没有多余贡献，\(g(n,j)=g(n,j-1)\)。
否则可以发现如果一个数有多余贡献，那么 \(p_j\) 是这个数的最小质因子，把这些数除以 \(p_j\) 要所有数的质因子都 \(\ge p_j\)。
但是直接递归会多算小于 \(p_j\) 的质数，所以要加回来。
观察这个式子，可以发现后面的部分出现必须满足 \(p_j\le \sqrt n\)，范围很小可以线筛预处理。
因为 n 很大，不能一个一个算过去，但是根据观察发现很多的 \(\frac{n}{p_j}\) 是相同的，所以有效的 n 只有根号个。
接下来考虑求值的问题，设函数 S，\(S(n,j)=\sum_{i=1}^n f(i)(\min_{p|i} p>p_j)\)。
还是分成质数和合数，因为 \(f\) 和 \(f'\) 在质数处取值相同，就是 \(g(n,|P|)\)，因为算多了前 \(j\) 个，减掉就好。
偶数部分按照上面分析的枚举最小因数及次数，这部分是：
最终答案是 \(S(n,0)+f(1)\)。
代码：
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
ll n,sq,s1[N],s2[N],w[N],g1[N],g2[N],id1[N],id2[N];
int cnt,p[N],m;
bool vis[N];
void init()
{
for(int i=2;i<=sq;i++)
{
if(!vis[i]) p[++cnt]=i;
for(int j=1;i*p[j]<=sq;j++)
{
vis[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
for(int i=1;i<=cnt;i++)
{
s1[i]=(s1[i-1]+p[i])%mod;
s2[i]=(s2[i-1]+1ll*p[i]*p[i])%mod;
}
}
ll get1(ll x)
{
x%=mod;
return x*(x+1)/2%mod;
}
ll get2(ll x)
{
x%=mod;
return x*(x+1)/2%mod*(2*x+1)%mod*333333336%mod;
}
int id(ll x)
{
if(x<=sq) return id1[x];
return id2[n/x];
}
ll s(ll x,int j)
{
if(p[j]>x) return 0;
ll ans=(g2[id(x)]-g1[id(x)]-s2[j]+s1[j])%mod;
for(int i=j+1;i<=cnt&&1ll*p[i]*p[i]<=x;i++)
{
for(ll e=1,v=p[i];v<=x;v*=p[i],e++)
{
ans=(ans+v%mod*(v%mod-1)%mod*(s(x/v,i)+(e>1))%mod)%mod;
}
}
return ans;
}
int main()
{
scanf("%lld",&n);
sq=sqrt(n);
init();
for(ll l=1;l<=n;l++)
{
ll r=(n/(n/l));
w[++m]=n/l;
g1[m]=get1(w[m])-1,g2[m]=get2(w[m])-1;
// printf("%d %d\n",g1[m],g2[m]);
if(w[m]<=sq) id1[w[m]]=m;
else id2[n/w[m]]=m;
l=r;
}
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=m&&1ll*p[i]*p[i]<=w[j];j++)
{
g1[j]=(g1[j]-p[i]*(g1[id(w[j]/p[i])]-s1[i-1]))%mod;
g2[j]=(g2[j]-1ll*p[i]*p[i]%mod*(g2[id(w[j]/p[i])]-s2[i-1]))%mod;
}
}
printf("%lld",(s(n,0)+1+mod)%mod);
return 0;
}
5.2. 例题
[loj6235]区间素数个数
相当于求 \(\sum_{i=1}^n [i\in P]\)，视作函数 \(f(i)\)。
完全积性函数取 \(f'(i)=1\)，然后按照上面的东西求 \(g(n,j)\)。
因为每个位置的值都是 1，所以式子退化为 \(g(n,j)=g(n,j-1)-(g(\frac{n}{p_j},j-1)-(j-1))\)
因为合数没有贡献，所以答案就是 \(g(n,0)\)
[loj053]简单的函数
可以发现奇质数是 \(x-1\) 所以可以拆成两个函数 \(f1(i)=1,f2(i)=i\)，按照上面的过程求就行了。
注意，这里有一个 2，因为它只能贡献到 \(j=0\)，所以最后把差补上就行了，中间其实没有影响。
浙公网安备 33010602011771号