自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:10:28，当前版本为作者最后更新于2019-07-17 21:03:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

updated

好不容易终于把这题阿了，于是来写一篇题解。。

---

第 $n$ 行第一类斯特林数的生成函数为

$$x^{\overline n}=\prod\limits_{i=0}^{n-1}(x+i)=\sum\limits_{i=0}^n\begin{bmatrix} n\\i\end{bmatrix}x^i $$

所以我们只需要求出那个连续乘积就好了

考虑倍增。

$$x^{\overline {2n}}=x^{\overline n}(x+n)^{\overline n} $$

也就是

$$\prod\limits_{i=0}^{2n-1}(x+i)=\prod\limits_{i=0}^{n-1}(x+i)\prod\limits_{i=0}^{n-1}(x+n+i) $$

那么只要能给定一个 $n$ 次多项式 $f(x)$，快速计算出 $f(x+k)$ 就行。

为了方便下面表述，我们设 $a_i=[x^i]f(x)$。

$$f(x+k)=\sum\limits_{i=0}^na_i(x+k)^i$$ $$=\sum\limits_{i=0}^na_i\sum\limits_{j=0}^i\binom{i}{j}x^jk^{i-j} $$$$= \sum\limits_{i=0}^nx^i\sum\limits_{j=i}^n \binom{j}{i}k^{j-i}a_j $$$$=\sum\limits_{i=0}^n\frac{x^i}{i!}\sum\limits_{j=i}^{n}\frac{k^{j-i}}{(j-i)!}j!a_j $$

别的大佬都说这个式子显然是卷积，没有具体写出来，这里就写一下吧，，

设

$$g(x)=\sum\limits_{i=0}^n\frac{k^i}{i!}x^{n-i}$$ $$h(x) = \sum\limits_{i=0}^ni!a_ix^i$$

那么只需要将 $g(x)$ 和 $h(x)$ 乘起来，然后左移 $n$ 位 ( 也就是将 $i$ 次项系数变为 $n+i$ 次项系数 ) 之后，第 $i$ 次都乘上 $i!$ 就是我们想要的 $f(x+k)$ 了。

当然，倍增过程中还要有计算 $x^{\overline n}(x+n)$ 的情况，暴力线性算一下即可。

时间复杂度

$$T(n)=T(n/2)+\Theta(n\log n)=\Theta(n \log n)$$

Code：

#pragma GCC optimize (2)
#pragma GCC optimize ("unroll-loops")
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 524292
#define ll long long
#define reg register
#define p 167772161
using namespace std;

void print(int x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

int rt[N],rev[N],fac[N],ifac[N];
int siz;

void init(int n){
    int w,lim = 1;
    while(lim<=n) lim <<= 1,++siz;
    for(reg int i=1;i!=lim;++i) rev[i] = (rev[i>>1]>>1)|((i&1)<<(siz-1));
    w = power(3,(p-1)>>siz);
    fac[0] = fac[1] = ifac[0] = ifac[1] = rt[lim>>1] = 1;
    for(reg int i=lim>>1|1;i!=lim;++i) rt[i] = (ll)rt[i-1]*w%p;
    for(reg int i=(lim>>1)-1;i;--i) rt[i] = rt[i<<1];
    for(reg int i=2;i<=n;++i) fac[i] = (ll)fac[i-1]*i%p;
    ifac[n] = power(fac[n],p-2);
    for(reg int i=n-1;i;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
}

inline void dft(int *f,int lim){
    static unsigned long long a[N];
    reg int x,shift = siz-__builtin_ctz(lim);
    for(reg int i=0;i!=lim;++i) a[rev[i]>>shift] = f[i];
    for(reg int mid=1;mid!=lim;mid<<=1)
    for(reg int j=0;j!=lim;j+=(mid<<1))
    for(reg int k=0;k!=mid;++k){
        x = a[j|k|mid]*rt[mid|k]%p;
        a[j|k|mid] = a[j|k]+p-x;
        a[j|k] += x;
    }
    for(reg int i=0;i!=lim;++i) f[i] = a[i]%p;
}

inline void idft(int *f,int lim){
    reverse(f+1,f+lim);
    dft(f,lim);
    int x = p-((p-1)>>__builtin_ctz(lim));
    for(reg int i=0;i!=lim;++i) f[i] = (ll)f[i]*x%p;
}

inline void composite(const int *f,int n,int c,int *R){ //由 f(x) 计算 f(x+c)
    static int g[N],h[N];
    g[0] = 1,h[0] = 0;
    for(reg int i=1;i<=n;++i){
        g[i] = (ll)g[i-1]*c%p;
        h[i] = (ll)f[i]*fac[i]%p;
    }
    for(reg int i=2;i<=n;++i) g[i] = (ll)g[i]*ifac[i]%p;
    reverse(g,g+n+1);
    int lim = 1<<(32-__builtin_clz(n<<1));
    memset(g+n+1,0,(lim-n)<<2);
    memset(h+n+1,0,(lim-n)<<2);
    dft(g,lim),dft(h,lim);
    for(reg int i=0;i!=lim;++i) g[i] = (ll)g[i]*h[i]%p;
    idft(g,lim);
    for(reg int i=0;i<=n;++i) R[i] = (ll)g[i+n]*ifac[i]%p;
}

void solve(int *f,int n){
    static int g[N],st[30];
    int lim = 1,top = 0;
    while(n){
        st[++top] = n;
        n >>= 1;
    }
    n = f[1] = st[top--];
    while(top--){
        while(lim<=(n<<1)) lim <<= 1;
        composite(f,n,n,g);
        memset(g+n+1,0,(lim-n)<<2);
        dft(f,lim),dft(g,lim);
        for(reg int i=0;i!=lim;++i) f[i] = (ll)f[i]*g[i]%p;
        idft(f,lim);
        n <<= 1;
        if(n==st[top+1]) continue;
        f[n+1] = f[n];
        for(reg int i=n;i;--i) f[i] = (f[i-1]+(ll)f[i]*n)%p;
        f[0] = (ll)f[0]*n%p;
        ++n;
    }
}

int f[N];
int n;

int main(){
    scanf("%d",&n);
    init(n<<1);
    solve(f,n);
    for(reg int i=0;i<=n;++i) print(f[i]),putchar(' ');
    return 0;   
}