斯特林数及反演
以前根本不知道斯特林反演，斯特林数也忘的差不多了，复习一下。
快乐斯特林：
第一类斯特林数
记作 \(\displaystyle{a\brack b}\)，表示从 \(a\) 个数中选出 \(b\) 个环的方案数。
-
\(\displaystyle {a\brack b}=\displaystyle{a-1\brack b-1}+(a-1){a-1\brack b}\)
插入一个数，要么新建环，要么插在任意位置。
-
$\displaystyle\sum_{i=0}^n {n\brack i}=n! $
看作排列的置换环。
-
\(\displaystyle {a\brack 1}=(a-1)!\;\;{a\brack a-1}=\binom a2\)
第一个就是圆排列，第二个是选出两个放一起。
问不同前缀 \(\max\) 数量 \(=A\) 且不同后缀 \(\max\) 数量 \(=B\) 的 \(1\sim n\) 排列数量。
\(A,B\le 100,n\le 10^5\)
题解：
首先，前后缀完全分离，因为在访问到最大值 \(n\) 之后不会产生新的最大值。
可以将其分别离散化，然后最后乘组合数。
所以问题转化为求不同前缀 \(\max\) 数量 \(=A\) 的 \(1\sim n\) 排列数量。
设前缀最大值依次为 \(c_1,\dots,c_A\)。
那么可以把 \([c_i,c_{i+1}-1](i\in[1,A-1])\) 看作环，因为最大值确定了环的一个点。
更容易理解的，从 \([1,n]\) 选出 \(A\) 个环，然后将其按最大值排序，并将最大值放在首位依次放入，不难发现是双射。
回归到原题。
发现其所可以不用枚举 \(n\) 的位置。
答案就算先拿出 \(n\)，然后从 $n-1 $ 个数中选出 \(A+B-2\) 环，再从 \(A+B-2\) 个环中选 \(A-1\) 个放左边，其余放右边。
所以 \(\displaystyle {n-1\brack A+B-2}\binom{A+B-2}{A-1}\) 。
第二类斯特林数
记作 \(\displaystyle{a\brace b}\)，表示从 \(a\) 个数中选出 \(b\) 个非空子集的方案数。
-
\(\displaystyle {a\brace b}=\displaystyle{a-1\brace b-1}+b{a-1\brace b}\)
插入一个数，要么新建子集，要么插在任意子集。
-
\(\displaystyle{a\brace 2}=2^{a-1}-1\)
判断 \(2\sim a\) 的数是否与 \(1\) 在同一子集，减去一个全在一起的方案。
-
\(\displaystyle {a\brace b}=\frac{1}{b!}\sum_{i=0}^b(-1)^i \binom{b}{i}(b-i)^a=\sum_{i=0}^b(-1)^i\frac{(b-i)^a}{i!(b-i)!}\)
容斥。
-
\(\displaystyle{a+1\brace b+1}=\sum_{i=b}^a\binom a{a-i}{i\brace b}\)
枚举哪些数与 \(1\) 在同一集合。
Codeforces 1342 E
在 \(n \times n\) 的棋盘上放 \(n\) 个车，要求所有格子均能被车攻击、恰好有 \(k\) 对车能互相攻击。\(n\le 10^5,k\le \frac12n(n-1)\)
题解：
一个诈骗点：你的車不是炮。
首先，必定满足所有行都有车或所有列都有，否则就会有格子攻击不到。
其次，我们可以通过简单容斥，将问题转化为只算每行出现一次\(\times 2\) \(-\)每一行每一列都出现一次。
（只在 \(k=0\) 才有东西要减，而且 \(k=0\) 时只要减 \(n!\)，而 \(k=0\) 的答案就是 \(n!\)。）
不难发现 \(k\ge n\) 时答案 \(=0\)。互相攻击的车的对数为 \(n\) \(-\) 出现车的列数。
把出现车的列看作集合，不难写出答案：\(\displaystyle \binom{n}{n-k}{n\brace k}(n-k)!\)
上升下降幂
定义
\[a^{\overline{b}}=\prod_{i=a}^{a+b-1}i \\ \]\[a^{\underline{b}}=\prod_{i=a-b+1}^b i\\ \]注意 \(a\in \mathbb{R},b\in \mathbb{N}\)。也可以此拓展组合数的定义域。
-
\(a^\overline{x+y}=a^\overline x(a+x)^\overline y，a^\underline{x+y}=a^\underline x(a-x)^\underline y\)
(变量名只是为了好看)
-
\(a^\overline{b}=(-1)^b(-a)^{\underline{b}},a^\overline b=(a+b-1)^\underline{b}\)
\(a^\underline{b}=(-1)^b(-a)^{\overline{b}},a^\underline b=(a-b+1)^\overline{b}\)
-
\(\displaystyle \binom ab b^\underline i=\frac{a!}{(a-b)!(b-i)!}=\binom{a-i}{b-i}a^\underline i\)
-
\((a+1)^\underline b-a^\underline {b}=b a^\underline {b-1}\)
-
\(\displaystyle \sum_{i=a}^{b-1} i^\underline{t}=\displaystyle t!\sum_{i=a}^{b-1} \binom{i}{t}=t!\left(\binom{b}{t+1}-\binom{a}{t+1}\right)=\frac{b^\underline {t+1}-a^\underline{t+1}}{t+1}\)
-
\(\displaystyle(x+y)^\overline{a}=\sum_{i=0}^a\binom{a}ix^\overline{i}y^\overline{a-i},\displaystyle(x+y)^\underline{a}=\sum_{i=0}^a\binom{a}ix^\underline{i}y^\underline{a-i}\)
\(\displaystyle\sum_{i=0}^a\binom{a}ix^\overline{i}y^\overline{a-i}=a!\displaystyle\sum_{i=0}^a\frac 1{i!(a-i)!}x^\overline{i}y^\overline{a-i}=a!\displaystyle\sum_{i=0}^a\binom{x}i\binom{y}{a-i}=a!\binom{x+y}a=(x+y)^\overline{a}\)
?
给定 \(n,m,a_{1\sim n}\)，求有多少个序列 \(b_{1\sim n}\) 满足 \(a_i\le b_i\le m(i\in[1,n]) ∧ b_i\le b_{i+1}(i\in[1,n))\)
\(n\le 5000,0\le a_i,m\le 10^9\)
题解：
首先让 \(a\) 做个前缀 \(\max\)，可以发现不影响答案。
设 \(f_{i,j}\) 表示做了前 \(i\) 位最后一位为 \(j\) 的方案数。
不难得出 \(\displaystyle f_{i,j}=\sum_{p=a_{i-1}}^m f_{i-1,p}\) ，答案就是 \(f_{n+1,m}\)。
注意到 \(f_i\) 可以写成一个 \(i-1\) 次多项式：把它写成下降幂 \(\displaystyle \sum_{j=0}^{i-1}g_{i,j} x^\underline{j}=F_i(x)=f_{i,x}\)。
\[\begin{aligned} F_{i+1}(x)&=\sum_{y=a_i}^x\sum_{j=0}^{i-1}g_{i,j} y^\underline{j}\\ &=\sum_{j=0}^{i-1}g_{i,j} \sum_{y=a_i}^xy^\underline{j}\\ &=\sum_{j=0}^{i-1}g_{i,j} \frac{(x+1)^\underline{j+1}-a_i^\underline{j+1}}{j+1}\\ &=\sum_{j=0}^{i-1}\frac {g_{i,j}}{j+1}(x^\underline{j+1}+(j+1)x^\underline j-a_i^\underline{j+1}) \end{aligned} \]\[\begin{aligned} \sum_{j=0}^{i}g_{i+1,j}x^\underline j&=\sum_{j=0}^{i-1}\frac {g_{i,j}}{j+1}(x^\underline{j+1}+(j+1)x^\underline j-a_i^\underline{j+1})\\ &=-\sum_{j=1}^{i}\frac{g_{i,j-1}-a_i^\underline j}j+g_{i,0}+\sum_{j=1}^i \left(\frac{g_{i,j-1}}{j}+g_{i,j}\right)x^\underline j \end{aligned} \]可以 $O(n^2) $ 推。
上升下降幂与普通幂的转化
-
\(\displaystyle x^n=\sum_{i=0}^n{n\brace i}x^\underline i\)
归纳。\(n=0\) 显然。
\(n\ge 1\) 时：
\[\begin{aligned} \sum_{i=0}^n{n\brace i}x^\underline i&=\sum_{i=0}^n\left({n-1\brace i-1}x^\underline i+i{n-1\brace i}x^\underline i\right)\\ &=\sum_{i=0}^{n-1}{n-1\brace i}x^\underline {i+1}+\sum_{i=0}^{n-1}i{n-1\brace i}x^\underline i\\ &=\sum_{i=0}^{n-1}(x-i){n-1\brace i}x^\underline {i}+\sum_{i=0}^{n-1}i{n-1\brace i}x^\underline i\\ &=\sum_{i=0}^{n-1}x{n-1\brace i}x^\underline {i}=x\sum_{i=0}^{n-1}{n-1\brace i}x^\underline {i}\\ &=x^n \end{aligned} \] -
\(\displaystyle x^\overline n=\sum_{i=0}^n{n\brack i}x^ i\)
归纳。\(n=0\) 显然。
\(n\ge 1\) 时：
\[\begin{aligned} \sum_{i=0}^n{n\brack i}x^i&=\sum_{i=0}^n\left({n-1\brack i-1}x^i+(n-1){n-1\brack i}x^i\right)\\ &=\sum_{i=0}^{n-1}{n-1\brack i}x^ {i+1}+(n-1)\sum_{i=0}^{n-1}{n-1\brack i}x^i\\ &=\sum_{i=0}^{n-1}x{n-1\brack i}x^i+(n-1)\sum_{i=0}^{n-1}{n-1\brack i}x^i\\ &=(x+n-1)\sum_{i=0}^{n-1}{n-1\brace i}x^i\\ &=x^\overline n \end{aligned} \]
其他转化可以由上文的
\[a^\overline{b}=(-1)^b(-a)^{\underline{b}},a^\overline b=(a+b-1)^\underline{b}\\ a^\underline{b}=(-1)^b(-a)^{\overline{b}},a^\underline b=(a-b+1)^\overline{b} \]得到。
标签：发现,忘光,复习,sum,displaystyle,overline,binom,brace,underline From： https://www.cnblogs.com/TOBapNwCJN/p/17161953.html如题，\(1\le n<2^{18}\)。
\(\displaystyle x^\overline n=\sum_{i=0}^n{n\brack i}x^ i\)。
可以用分治 NTT 或类似快速幂的方法求。
下面主要讲复杂度更优的第二种。
考虑如何快速令 \(x^\overline n\leftarrow x^\overline{2n}\)。
\(x^\overline{2n}=x^\overline n(x+n)^\overline n\)，令 \(\displaystyle x^\overline n=\sum_{i=0}^n a_i x^i\)。
\[\begin{aligned} (x+n)^\overline n&=\sum_{i=0}^n a_i (x+n)^i\\ &=\sum_{i=0}^n a_i\sum_{j=0}^i x^jn^{i-j}\binom{i}j\\ &=\sum_{j=0}^n \frac{x^j}{j!}\sum_{i=j}^n i! a_i n^{i-j}(i-j)!\\ \end{aligned} \]不难发现右边是减法卷积。
每次卷两次。
复杂度 \(T(n)=T(\frac n2)+\Theta(n\log n)=\Theta(n\log n)\)
第二类行也可以这么求，但有更优美的方法。