LG5409 第一类斯特林数·列 题解

Tag

多项式。

Preface

以后别人不会求这玩意的时候我就可以自信的说出“看我博客”这种话了……

Description

给定 \(n,k\)，对于所有 \(0 \leq i \leq n\)，求出 \(\left[\begin{matrix}i\\k\end{matrix}\right]\) 的值，对 \(167772161\) 取模。

\(\texttt{data range:} 1\leq n,k< 131072\).

Solution

下面令 \(s(n,k)\) 为第一类斯特林数 \(\left[\begin{matrix}i\\k\end{matrix}\right]\)。（说实话每一次打个矩阵挺扯淡的）

\(s(n,k)\) 读作"\(n\) 轮换 \(k\)"，表示的是 \(n\) 个有标号节点有 \(k\) 个轮换的方案数。

具体的，我们用一个置换来描述一个排列的话，那么我们可以得到若干个“环”，根据第一类斯特林数的定义，我们可以得到如果一个长为 \(n\) 的置换具有 \(k\) 个环，其方案数就是 \(s(n,k)\)。

接下来我们通过一些简单的组合意义证明 \(s(n,1)=(n-1)!,\sum\limits_is(n,i)=n!\) 这两个比较重要的结论。

我们可以将我们刚刚提到的置换具体的表示出来，比如 \((3)(41)(652)(87)\) 这样一个置换，将每一个环的最大的一个元素放到第一个的位置，然后按照第一个位置排序，然后将括号给去掉，就可以得到一个排列 \(34165287\)（注意这里并不是置换而是排列）。

不难发现我们随意改变一个值的位置就会变成另一个方案，所以此时证明了 \(\sum\limits_i s(n,i)=n!\)。

当 \(k=1\) 的时候，一定是最大的元素 \(n\) 在最前面，然后后面 \(n-1\) 个元素随便排，所以得到了 \(s(n,1)=(n-1)!\)。

回到本题。

不妨设 EGF \(F_k(z)\) 为有 \(k\) 个环的置换的个数，根据上面求得的

\[F_1(z) = \sum_n(n-1)!\dfrac{z^n}{n!}=\ln \dfrac{1}{1-z} \]

那么对于 \(F_k(z)\) 我们就很容易得到就是一个环的卷 \(k\) 次了，但是注意是无序的，所以要除去 \(k!\)，我们最终的答案的 EGF 就是：

\[\dfrac{\left(\ln \dfrac 1{1-z}\right)^k}{k!} \]

注意这里是 EGF，所以答案的最后需要乘上一个 \(i!\)。

对于我们导出的 \(F_1(z)\) 实际上对于 \(\sum\limits_is(n,i)=n!\) 有另一种解决方法。

不难设 EGF \(G(z)\) 表示长度为 \(n\) 的排列可以表示多少种置换，再根据上面的组合意义可以得到：

\[\exp(F_1(z))=G(z) \]

此时

\[G(z)=\sum_{n} n!\dfrac{z^n}{n!}=\dfrac 1{1-z} \]

所以 \(F_1(z) = \ln \dfrac 1{1-z}\)，之后就是相同的方法了。

求解方面可以通过向左移 \(\ln \dfrac 1{1-z}\) 的方法来用多项式 exp 来解决，最后再右移回去就可以了，时间复杂度为 \(O(n\lg n)\)。

但是实际上 \(O(n \lg n\lg k)\) 也过得去，甚至有时候比上面那种方法还快一点。

Code

using ll = long long;
using poly = vector;

const int N = 131072 * 2;
const int mod = 167772161, g = 3;
//const int mod = 998244353, g = 3;

inline void chk(int &x) {x -= mod; x += x >> 31 & mod;}
inline int mll(int x, int y) {return (ll) x * y % mod;}
inline int add(int x, int y) {chk(x += y); return x;}
inline int del(int x, int y) {return add(x, mod - y);}

inline int ksm(int x, int y) {
    int ret = 1;
    for(; y; y >>= 1, x = mll(x, x))
        if(y & 1) ret = mll(ret, x);
    return ret;
}

int fc[N], fv[N], inv[N];
inline void pref(const int lim) {
    fc[0] = 1;
    FOR(i, 1, lim) fc[i] = mll(fc[i - 1], i);
    fv[lim] = ksm(fc[lim], mod - 2);
    ROF(i, lim, 1) fv[i - 1] = mll(fv[i], i);
    FOR(i, 1, lim) inv[i] = mll(fv[i], fc[i - 1]);
    return ;
}

int rev[N << 1];
inline int getrev(const int n) {
    int len = 1, tim = -1;
    while(len < n) len <<= 1, tim++;
    FOR(i, 0, len - 1) rev[i] = rev[i >> 1] >> 1 | ((i & 1) << tim);
    return len;
}

void DFT(poly &F, int n) {
    F.resize(n);
    FOR(i, 0, n - 1) if(i < rev[i]) swap(F[i], F[rev[i]]);
    for(int i = 1; i < n; i <<= 1) {
        int gn = ksm(g, (mod - 1) / (i << 1));
        for(int j = 0, x, y, g0 = 1; j < n; j += (i << 1), g0 = 1)
        for(int k = 0; k < i; k++, g0 = mll(gn, g0)) {
            x = F[j + k], y = mll(F[i + j + k], g0);
            F[j + k] = add(x, y);
            F[i + j + k] = del(x, y);
        }
    }
    return ;
}

void IDFT(poly &F, int n) {
    DFT(F, n), reverse(F.begin() + 1, F.end());
    int iv = ksm(n, mod - 2);
    FOR(i, 0, n - 1) F[i] = mll(F[i], iv);
    return ;
}

poly operator + (poly A, poly B) {
    int l = max(A.size(), B.size());
    A.resize(l), B.resize(l);
    FOR(i, 0, l - 1) A[i] = add(A[i], B[i]);
    return A;
}

poly operator - (poly A, poly B) {
    int l = max(A.size(), B.size());
    A.resize(l), B.resize(l);
    FOR(i, 0, l - 1) A[i] = del(A[i], B[i]);
    return A;
}

poly operator * (poly A, int k) {
    FOR(i, 0, A.size() - 1) A[i] = mll(A[i], k);
    return A;
}

poly operator * (poly A, poly B) {
    int n = A.size() + B.size() - 1, len = getrev(n);
    DFT(A, len), DFT(B, len);
    FOR(i, 0, len - 1) A[i] = mll(A[i], B[i]);
    return IDFT(A, len), A.resize(n), A;
}

poly DI(const poly F) {
    poly G(F.size() - 1);
    FOR(i, 0, G.size() - 1) G[i] = mll(F[i + 1], i + 1);
    return G;
}

poly IG(const poly F) {
    poly G(F.size() + 1);
    FOR(i, 1, G.size() - 1) G[i] = mll(F[i - 1], inv[i]);
    return G;
}

poly INV(const poly F) {
    poly G; G.push_back(ksm(F[0], mod - 2));
    int n = F.size() << 1;
    for(int mx = 2; mx < n; mx <<= 1) {
        poly H = F; H.resize(mx);
        int len = getrev(mx << 1);
        DFT(G, len), DFT(H, len);
        FOR(i, 0, len - 1) G[i] = mll(G[i], del(2, mll(H[i], G[i])));
        IDFT(G, len), G.resize(mx);
    }
    return G.resize(F.size()), G;
}

poly LN(const poly F) {
    poly G = IG(DI(F) * INV(F));
    return G.resize(F.size()), G;
}

poly EXP(const poly F) {
    poly G; G.push_back(1);
    int n = F.size() << 1;
    for(int mx = 2; mx < n; mx <<= 1) {
        poly H = F;
        H.resize(mx), G.resize(mx);
        G = G * (poly(1, 1) - LN(G) + H);
    }
    return G.resize(F.size()), G;
}

poly Mulx(poly F, const int k) {
    poly G(F.size() + k);
    FOR(i, k, G.size() - 1) G[i] = F[i - k];
    return G;
}

poly Divx(poly F, const int k) {
    poly G(F.size() - k);
    FOR(i, 0, G.size() - 1) G[i] = F[i + k];
    return G;
}

void print(const poly F) {
    FOR(i, 0, F.size() - 1) cerr << F[i] << " \n"[i == ii];
}

inline void solve() {
    int n = rd, k = rd;
    int p = max(n, k);
    pref(p + 10);
    poly F;
    FOR(i, 0, n) F.push_back(1);
    F = LN(F);
    poly H = Divx(F, 1);
    H = EXP(LN(H) * k);
    F.clear(), F.resize(n + 1);
    FOR(i, k, n) F[i] = mll(H[i - k], fv[k]);
    FOR(i, 0, n) cout << mll(F[i], fc[i]) << ' ';
    return ;
}

Final

本来想用二元生成函数去解决的，但是运用的不是很熟练，还是只能拼来拼去的用，有没有老哥教教我怎么用二元生成函数啊。

自此，关于斯特林数的四道题全部完成了。