第一类斯特林数
生成函数
式子
\(f(x)=\prod\limits_{i=0}^{n-1}(x+i)\)
证明
使用数学归纳法。
递推式
式子
\(\left[\begin{matrix}n\\k\end{matrix}\right]=(n-1)\left[\begin{matrix}n-1\\k\end{matrix}\right]+\left[\begin{matrix}n-1\\k-1\end{matrix}\right]\)
证明
假设最后一个元素自己成为一个圆排列，或者最后一个元素插到前面的 \(n-1\) 的元素的前面(后面类似)，形成圆排列，也就是前面的每一个长度为 \(n\) 的圆排列提供了 \(n\) 个不同的方案来插入。
性质
1
\(n!=\sum\limits_{i=0}^n\left[\begin{matrix}n\\i\end{matrix}\right]\)
### 2
\(\left[\begin{matrix}n\\n-2\end{matrix}\right]=2\times C_n^3+3\times C_N^4\)
求行
倍增求解，多项式卷积，可以看洛谷的题解。
例题
题目1
P5408 【模板】第一类斯特林数·行
注意
卡常。
另外一定记得哪些函数需要取反，一个是
\(F(x)=LastFuntion_x\times x!\)
\(LastFunction\) 表示上一次倍增的函数
一个是
\(H(x)=\sum\limits_{i=0}^nF(i)\times G(n-i)\)
其中
\(G(x)=\frac{n^x}{x!}\)
代码
#include <cstdio>
using namespace std;
inline void swap (int &a, int &b) {
int c = a;
a = b,
b = c;
}
const int N = (262144 + 5) << 1, mod = 167772161, inver = 55924054;
inline int add (int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
inline int mns (int u, int v) { return u - v < 0 ? u - v + mod : u - v; }
inline int mul (int u, int v) { return 1LL * u * v % mod; }
inline int qpow (int u, int v) {
int tot = 1, base = u % mod;
while (v) {
if (v & 1) tot = mul (tot, base);
base = mul (base, base);
v >>= 1;
}
return tot;
}
int rev[N], sz, cnt2;
inline void NTT (int *a, int n, int bit, int flag) {
for (int i = 0; i < n; ++i) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
if (i > rev[i]) swap (a[i], a[rev[i]]);
}
for (int l = 2; l <= n; l <<= 1) {
int wi = qpow (flag ? inver : 3, (mod - 1) / l),
m = l / 2;
for (int *k = a; k != a + n; k += l) {
int w = 1;
for (int i = 0; i < m; ++i) {
int tmp = mul (k[i + m], w);
k[i + m] = mns (k[i], tmp);
k[i] = add (k[i], tmp);
w = mul (w, wi);
}
}
}
int tmp = qpow (n, mod - 2);
for (int i = 0; i < n && flag; ++i) {
a[i] = mul (a[i], tmp);
}
}
inline void MUL (int *a, int *b, int *c, int la, int lb) {
static int mula[N << 1], mulb[N << 1], n, bit;
n = 1,
bit = 0;
while (n < la + lb - 1) n <<= 1, ++bit;
for (int i = 0; i < la; ++i) mula[i] = a[i]; for (int i = la; i < n; ++i) mula[i] = 0;
for (int i = 0; i < lb; ++i) mulb[i] = b[i]; for (int i = lb; i < n; ++i) mulb[i] = 0;
NTT (mula, n, bit, false), NTT (mulb, n, bit, false);
for (int i = 0; i < n; ++i) mula[i] = mul (mula[i], mulb[i]);
NTT (mula, n, bit, true);
for (int i = 0; i < la + lb - 1; ++i) c[i] = mula[i];
}
int fac[N], invfac[N];
inline void init () {
fac[0] = 1, fac[1] = 1;
for (int i = 2; i <= (sz << 1); ++i) fac[i] = mul (fac[i - 1], i);
invfac[sz << 1] = qpow (fac[sz << 1], mod - 2);
for (int i = (sz << 1) - 1; i >= 0; --i) invfac[i] = mul (invfac[i + 1], i + 1);
}
inline void solve (int *a, int len) {
if (len == 1) { a[0] = 0, a[1] = 1; return ; }
static int f[N << 1], g[N << 1], h[N << 1], xd, l, r;
solve (a, len >> 1);
xd = len >> 1;
for (int i = 0; i <= xd; ++i) f[xd - i] = mul (a[i], fac[i]);
int tmp = 1;
for (int i = 0; i <= xd; ++i) g[i] = mul (tmp, invfac[i]), tmp = mul (tmp, xd);
MUL (f, g, h, xd + 1, xd + 1);
l = 0, r = xd; while (l < r) swap (h[l], h[r]), ++l, --r;
for (int i = 0; i <= xd; ++i) h[i] = mul (h[i], invfac[i]);
MUL (a, h, a, xd + 1, xd + 1);
if (len % 2) {
g[0] = len - 1, g[1] = 1;
MUL (a, g, a, len, 2);
}
}
int main () {
scanf ("%d", &sz);
init ();
static int ans[N << 1];
solve (ans, sz);
for (int i = 0; i <= sz; ++i) printf ("%d ", ans[i]);
return 0;
}
转载于:https://www.cnblogs.com/ChiTongZ/p/11398032.html
相关资源：JAVA上百实例源码以及开源项目
