《小 学 组 合 数 学》

嗯,这就是小学难度,起码我学这些东西的时候我是个小学生

线性求逆元

这个玩意要分两块讲,\(p\) 是模数。

线性求 \(1 \sim N\) 的逆元

对于一个 \(i\)

\[\text{设} a = \lfloor \frac{p}{i} \rfloor, \ b = p \bmod i, \]

\[ai + b \equiv 0 \pmod p, \]

\[\frac{i}{b} + \frac{1}{a} \equiv 0 \pmod p \ (\text{两边除以} \ ab) \]

\[\frac{i}{b} \equiv - \frac{1}{a} \pmod p \]

\[\frac{b}{i} \equiv -a \pmod p \]

\[bi^{-1} \equiv -a \pmod p \]

\[i^{-1} \equiv -ab^{-1} \pmod p \]

然后递推。

线性求任意 \(N\) 个数的逆元(注意到它可以用来求阶乘的逆元)

首先我们求出 \(N\) 个数的前缀积,记作 \(pre\)

定义 \(inv_i\)\(pre_i\) 的逆元。

然后我们求出 \(inv_N\)

最后我们利用逆元的性质,\(inv_i = inv_{i+1}a_{i+1}\)

对于第 \(i\) 个数,它的逆元是 \(inv_{i} \times pre_{i-1}\)\(pre_0 = 1\))。

本质不同排列

整体减空白。

分苹果

Section 1:正整数

假设我们有 \(N\) 个一样的苹果,要分给 \(M\) 个人。他们都饿了,所以每一个人至少要有一个苹果。求分法。

我们把 \(N\) 个苹果排成一排,有 \(N - 1\) 个空隙。苹果都是一样的,本质是在这 \(N - 1\) 个空隙中插入 \(M - 1\) 个板子(形成 \(M\) 个区间第, \(i\) 个区间给第 \(i\) 个人),答案总数是 \(\dbinom{N - 1}{M - 1}\)

Section 2:非负整数

还是苹果,还是人,但这次这些苹果是点心,所以有些人可以没有苹果。仍然求分法。

一个空隙里面可以插上多个苹果,怎么办呢?

我们拿 \(M\) 个反物质苹果过来(假设我们到达了无限),然后问题就转化成了 Section 1。

方案数是 \(\dbinom{N + M - 1}{M - 1}\)

热门相关:盛宠之嫡女医妃   护花猎王   锦衣   君归矣   萌妻太甜:总裁大人,别傲娇