数学随记

前言
组合数
第一类斯特林数
- 定义
- 性质
第二类斯特林数
- 定义
- 性质
  - 性质1
拉格朗日插值
克莱姆法则

需要填的坑：斯特林数、拉格朗日插值。

~~啊啊啊啊啊啊更不动了。~~

参考博客：gzy_cjoier

木示木干 orz

前言

随心所欲。

组合数

({nchoose k} imes k^{underline{m}}={n-mchoose k-m} imes n^{underline{m}})

组合数和下降幂相乘有优美的性质(虽然看起来没啥用)。

(overset{n}{underset{i=m}{sum}}{ichoose m}={n+1choose m+1})

希望看到这个式子能迅速反应，而不是想半天的杨辉三角。

其实还存在组合意义，考虑 (n+1) 个球分给 (m+1) 个人，用隔板法暴力求解就是 LHS，加个板，加个球表示最后一个位置隔出来的不要，就是 RHS。

(inom{n}{m} =[n&m=m]pmod{2})

其中& 表示按位与，用卢卡斯定理即可得证，此时是 (O(1)) 求解。

第一类斯特林数

定义

第一类斯特林数 (s(n,m)) 表示将 (n) 个不同元素构成 (m) 个圆排列的方案数，记为 (egin{bmatrix}n\ m end{bmatrix})。

有递推公式：

[egin{bmatrix}n\ m end{bmatrix}=egin{bmatrix}n-1\ m-1 end{bmatrix} +(n-1) imes egin{bmatrix}n-1\ m end{bmatrix} ]

性质

性质1

第一类斯特林数可以和阶乘扯上关系。

[n!=sum_{i=0}^negin{bmatrix}n\ i end{bmatrix} ]

性质2

下降幂。

[x^{underline{n}}=sum_{i=0}^n (-1)^{n-i}egin{bmatrix}n\ i end{bmatrix} ]

性质3

上升幂。

[x^{overline{n}}=sum_{i=0}^negin{bmatrix}n\ i end{bmatrix} x^i ]

第二类斯特林数

定义

第二类斯特林数 (s(n,m)) 表示将 (n) 个不同元素构成 (m) 个集合的方案数，记为 (egin{Bmatrix}n\mend{Bmatrix})。

有递推公式：

[egin{Bmatrix}n\mend{Bmatrix}=egin{Bmatrix}n-1\m-1end{Bmatrix}+m imes egin{Bmatrix}n-1\mend{Bmatrix} ]

边界：(egin{Bmatrix}0\0end{Bmatrix}=1)

还有一个经典容斥：

[egin{Bmatrix}n\mend{Bmatrix}=frac{1}{m!}sum_{i=0}^{m}(-1)^iinom{m}{i}(m-i)^n ]

性质

性质1

幂与阶乘、组合数、下降幂的转换。

[n^m=sum_{i=0}^megin{Bmatrix}m\iend{Bmatrix} imes i! imes inom{n}{i} ]

我们可以用这个来求解自然数幂和：

[egin{aligned}S(n)&=sum_{i=1}^n i^m\&=sum_{i=1}^n sum_{j=0}^k egin{Bmatrix}m\jend{Bmatrix}cdot j!cdot inom{i}{j}\&=sum_{j=0}^kegin{Bmatrix}m\jend{Bmatrix}cdot j!cdot inom{n+1}{j+1}end{aligned} ]

插值落泪 qwq

上面那个还可以写成：

[n^m=sum_{i=0}^megin{Bmatrix}m\iend{Bmatrix} imes n^{underline{i}} ]

在 [省选联考 2020 A 卷] 组合数问题用到。

(To be continued.)

拉格朗日插值

引

我们知道，对于横坐标互不相同的 (n+1) 个点，我们可以唯一确定一个 (n) 次多项式，那么我们如何求解呢？

高斯消元！显然这不够优秀，需要 (O(n^3))，而拉格朗日插值可以做到 (O(n^2))。

(How can you make it?)——DDG

普通版本

令这个多项式为 (f(x))，则其在横坐标为 (k) 时的值为：

[sum_{i=0}^ny_iprod_{j ot=i} frac{k-x_j}{x_i-x_j} ]

完全是构造嘛！我们把 (x_i) 代入进去，发现完全满足等于 (y_i) 的条件。

乍一看求需要逆元，所以是 (O(n^2log_2n)) 的，但其实可以累计起来，最后求一次逆元。

时间复杂度是 (O(n^2+nlog_2n)≈O(n^2))。

代码

int qpow(int x,int y)
{
	int ret = 1;
	while(y){if(y & 1) ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
	return ret;
}


int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = Read(); k = Read();
	for(int i = 1;i <= n;++ i) x[i] = Read(),y[i] = Read();
	for(int i = 1;i <= n;++ i)
	{
		int nm = y[i],tmp = 1;
		for(int j = 1;j <= n;++ j)
			if(i != j) nm = 1ll * nm * (k-x[j]) % MOD,tmp = 1ll * tmp * (x[i]-x[j]) % MOD;
		ans = (ans + 1ll * nm * qpow(tmp,MOD-2)) % MOD;
	}
	Put((ans+MOD)%MOD);
	return 0;
}

特殊版本

在 (x) 取值连续时的做法，可以达到 (O(n))。

我们把式子写出来就知道了，用 (i) 替换 (x_i)。

[sum_{i=0}^ny_iprod_{j ot=i} frac{k-j}{i-j} ]

这个 (prod) 里面的分子分母不是显然可以用类似阶乘的方法预处理吗？但是要注意正负号。

当然逆元也要预处理，不然就是 (O(nlog_2n)) 了。

重心拉格朗日插值