Description：

对每个 $i\in [1,n]$ 求出每一个环的长度都在给出的集合 $S$ 中的排列个数。

$1\leqslant n\leqslant 10^5$

Solution：

先列式子，枚举环的个数 $k$ ，长为 $l$ 的只有一个环的排列有 $(l-1)!$ 个： $$ \begin{align} f_i&=\sum_{k=1}^\infty\frac{\sum_{l_1+l_2+\cdots+l_k=i}\binom i{l_1,l_2,\dots,l_k}\prod_{j=1}^k[l_j\in S](l_j-1)!}{k!}\\ &=\sum_{k\geqslant 1}i!\frac{\sum_{l_1+l_2+\cdots+l_k=i}\prod_{j=1}^k\frac{[l_j\in S]}{(l_j-1)!}}{k!} \end{align} $$ 设 $S(x)$ 为 $s_i=\frac{[i\in S]}{(i-1)!}$ 的普通生成函数。 $$ \frac{f_i}{i!}=\sum_{k\geqslant 1}\frac{S^k}{k!}=e^S $$ 于是多项式求 $\exp$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 400010

#define P 950009857

#define G 7

int fac[MAXN];

inline int rd()

{

    register int res = 0;register char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

    return res;

}

int S[MAXN];

int a[MAXN];

int rev[MAXN];

int ww[MAXN << 1],*g = ww + MAXN;

int power(int a,int b)

{

    int res = 1;

    for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

    return res;

}

int inver(int a){return power(a,P - 2);}

int init(int n)

{

    int l = 0,len = 1;

    for(;len <= n;len = len << 1)++l;

    for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

    g[0] = g[-len] = 1;g[1] = g[1 - len] = power(G,(P - 1) / len);

    for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

    return len;

}

void NTT(int f[],int l,int type)

{

    for(int i = 0;i < l;++i)

    {

        if(i < rev[i])swap(f[i],f[rev[i]]);

    }

    for(int i = 2;i <= l;i = i << 1)

    {

        int wn = g[type * l / i];

        for(int j = 0;j < l;j += i)

        {

            int w = 1;

            for(int k = j;k < j + i / 2;++k)

            {

                int u = f[k],t = 1ll * w * f[k + i / 2] % P;

                f[k] = (u + t) % P;

                f[k + i / 2] = (u - t + P) % P;

                w = 1ll * w * wn % P;

            }

        }

    }

    if(type == -1)

    {

        int ni = power(l,P - 2);

        for(int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % P;

    }

    return;

}

int c[MAXN];

void poly_inv(int deg,int a[],int b[])

{

    if(deg == 1){b[0] = power(a[0],P - 2);return;}

    poly_inv((deg + 1) >> 1,a,b);

    int l = init(deg * 2);

    for(int i = 0;i < deg;++i)c[i] = a[i];

    for(int i = deg;i < l;++i)c[i] = 0;

    NTT(c,l,1);NTT(b,l,1);

    for(int i = 0;i < l;++i)b[i] = (2ll * b[i] - 1ll * c[i] * b[i] % P * b[i] % P + P) % P;

    NTT(b,l,-1);

    for(int i = deg;i < l;++i)b[i] = 0;

    return;

}

int lnt[MAXN];

void poly_ln(int deg,int a[],int b[])

{

    poly_inv(deg,a,lnt);

    for(int i = 0;i < deg;++i)b[i] = a[i];

    for(int i = 0;i < deg;++i)b[i] = 1ll * (i + 1) * b[i + 1] % P;

    int l = init(deg * 2);

    NTT(b,l,1);NTT(lnt,l,1);

    for(int i = 0;i < l;++i)b[i] = 1ll * b[i] * lnt[i] % P;

    NTT(b,l,-1);

    for(int i = deg - 1;i >= 1;--i)b[i] = 1ll * inver(i) * b[i - 1] % P;b[0] = 0;

    for(int i = 0;i < l;++i)lnt[i] = 0;

    for(int i = deg;i < l;++i)b[i] = 0;

    return;

}

int expt[MAXN];

void poly_exp(int deg,int a[],int b[])

{

    if(deg == 1)

    {

        b[0] = 1;

        return;

    }

    poly_exp((deg + 1) >> 1,a,b);

    poly_ln(deg,b,expt);

    for(int i = 0;i < deg;++i)expt[i] = (a[i] - expt[i] + P) % P;

    expt[0] = (expt[0] + 1) % P;

    int l = init(deg * 2);

    NTT(expt,l,1);NTT(b,l,1);

    for(int i = 0;i < l;++i)b[i] = 1ll * b[i] * expt[i] % P;

    NTT(b,l,-1);

    for(int i = 0;i < l;++i)expt[i] = 0;

    for(int i = deg;i < l;++i)b[i] = 0;

    return;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= m;++i)S[rd()] = 1;

    for(int i = 1;i <= n;++i)S[i] = 1ll * S[i] * inver(i) % P;

    poly_exp(n + 1,S,a);

    for(int i = 1,cur = 1;i <= n;++i,cur = 1ll * cur * i % P)printf("%d\n",1ll * a[i] * cur % P);

    return 0;

}