第二类斯特林数
第二类斯特林数 \(\begin{Bmatrix}n\\k\end{Bmatrix}\)，意义为将 \(n\) 个不用的元素分为 \(k\) 个非空子集的方案数。
有 \(\displaystyle\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix}\)，边界为 \(\begin{Bmatrix}n\\0\end{Bmatrix}=\lbrack n=0\rbrack\).
- \(\displaystyle x^n=\sum_{k=0}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline k}\)
\(x^{\underline k}\) 是 \(x\) 的 \(k\) 次下降幂，即 \(\displaystyle\prod_{i=x}^{x-k+1}i=\frac{x!}{(x-k)!}\).
即用 \(x\) 种颜色给 \(n\) 个点染色，共 \(x^n\) 种方案，同样表示的是总共染 \(k\) 种颜色，把 \(n\) 个点分为这 \(k\) 个集合的方案数。
Cards
进行 \(n\) 次操作：你有 \(\large\frac{1}{m}\) 的概率获得 \(1\) 贡献。
记贡献为 \(x\)，求 \(x^k\) 的期望值。
答案对 \(998244353\) 取模。
\(1\le n,m<998244353\)，\(1\le k\le 5000\).
令 \(p=\large\frac{1}{m}\)，答案是
用上面的式子将 \(i^k\) 展开：
下降幂有一个性质：\(\displaystyle \binom{n}{i}i^{\underline j}=\binom{n-j}{i-j}n^{\underline j}\)
证明这个式子可以直接展开：
-
左 \(\displaystyle=\frac{n!}{i!(n-i)!}\cdot\frac{i!}{(i-j)!}=\frac{n!}{(n-i)!(i-j)!}\)
-
右 \(\displaystyle=\frac{(n-j)!}{(n-i)!(i-j)!}\cdot\frac{n!}{(n-j)!}=\frac{n!}{(n-i)!(i-j)!}\)
可证上式。
继续往下做：
后面是二项式定理，即
得到
\(n^{\underline j}\) 可以直接计算，时间复杂度 \(O(k^2)\).
提一下二项式反演的其中两个类型：
- \((1).\space\displaystyle f(n)=\sum_{i=0}^{n}(-1)^i\binom{n}{i}g(i)\)
- \((2).\space\displaystyle f(n)=\sum_{i=0}^{n}\binom{n}{i}g(i)\)
证明：此处令 \(h(n)=(-1)^ng(n)\)，把它代入 \((1)\) 中：
\(\displaystyle h(n)=\sum_{i=0}^{n}(-1)^i\binom{n}{i}f(i)\)
同除 \((-1)^n\)，整理可得 \((2)\).
通项公式
证明：仍然用到自然数幂转下降幂的式子：
二项式反演，设
展开 \(g(m)\)：
拆开组合数：
即第二类斯特林数的通项公式。
P5395 第二类斯特林数·行
求出所有的 \(\begin{Bmatrix}n\\i\end{Bmatrix},i\in\lbrack0,n\rbrack\).
答案对 \(167772161=5\times 2^{25}+1\) 取模。
\(1\le n\le 2\times 10^5\).
通项公式不就是卷积的形式吗？
将 \(\displaystyle f(x)=\frac{x^n}{x!}\) 与 \(\displaystyle g(x)=\frac{(-1)^x}{x!}\) 卷起来即可。时间复杂度 \(O(n\log n)\).
贴份代码。
#include<bits/stdc++.h>
#define N 1<<20
#define P 167772161
using namespace std;
int qpow(int k,int b){
int ret=1;
while(b){
if(b&1)ret=1ll*ret*k%P;
k=1ll*k*k%P,b>>=1;
}
return ret;
}
int f[N],g[N],h[N];
int n,lim=1,r[N];
int gn,tp,inv;
void ntt(int *x,int lim,int opt){
for(int i=0;i<lim;i++)
if(r[i]<i)swap(x[i],x[r[i]]);
for(int m=2,k=1;m<=lim;m<<=1,k<<=1){
gn=qpow(3,(P-1)/m);
for(int i=0;i<lim;i+=m){
for(int j=0,g=1;j<k;j++,g=1ll*g*gn%P){
tp=1ll*x[i+j+k]*g%P;
x[i+j+k]=(x[i+j]-tp+P)%P;
x[i+j]=(x[i+j]+tp)%P;
}
}
}
if(opt==-1){
reverse(x+1,x+lim),inv=qpow(lim,P-2);
for(int i=0;i<lim;i++)
x[i]=1ll*x[i]*inv%P;
}
}
int fac[N],ifac[N];
int main(){
cin>>n,fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=1ll*fac[i-1]*i%P;
ifac[n]=qpow(fac[n],P-2);
for(int i=n-1;i;i--)
ifac[i]=1ll*ifac[i+1]*(i+1)%P;
for(int i=0;i<=n;i++){
f[i]=1ll*qpow(i,n)*ifac[i]%P;
g[i]=(i&1)?P-ifac[i]:ifac[i];
}
n++;
while(lim<(n<<1))lim<<=1;
for(int i=0;i<lim;i++)
r[i]=(r[i>>1]>>1)+(i&1)*(lim>>1);
ntt(f,lim,1),ntt(g,lim,1);
for(int i=0;i<lim;i++)
h[i]=1ll*f[i]*g[i]%P;
ntt(h,lim,-1);
for(int i=0;i<n;i++)
printf("%d ",h[i]);
printf("\n");
return 0;
}
其他例题
P6620 [省选联考 2020 A 卷] 组合数问题
求
\(f(k)\) 为一个 \(m\) 次多项式。
答案对 \(p\) 取模。
\(1\le n,x,p\le 10^9\)，\(0\le a_i\le 10^9\)，\(0\le m\le \min(n,1000)\).
直接展开 \(f(k)\)：
\(\displaystyle k^i=\sum_{j=0}^{k}\begin{Bmatrix}i\\j\end{Bmatrix}\binom{k}{j}j!\)，此处不妨令上界为 \(i\)，代进去：
考虑合并一下两个组合数，就是先在 \(n\) 个里面选 \(k\) 个，再从 \(k\) 个里面选 \(j\) 个。
也就是先在 \(n\) 个里面选 \(j\) 个，然后再从 \(n-j\) 个里选剩下的 \(k-j\) 个，即 \(\displaystyle\binom{n-j}{k-j}\binom{n}{j}\).
后面长得很像二项式定理：
也就是
\(\displaystyle\binom{n}{j}j!=n^{\underline j}\) 递推计算。时间复杂度 \(O(m^2)\).