题解 P7265 【Look At The Sky】

· · 题解

套路二合一

n^kans=\sum\limits_{G}\sum\limits_{v\in G} v^k =\sum\limits_{v=1}^n v^kf_v 考虑选 $v$ 个点硬点他们连通，有 $f_v=\tbinom{n}{v}g_v h_{n-v}$，其中 $g_v$ 表示 $v$ 个点连通的方案数， $h_{v}$ 表示 $v$ 个点的方案数 考虑每条边选或不选有 $h_v=2^{\frac{v(v-1)}{2}} 于是我们 $O(n\log n)$ 计算出所有 $f_v

接下来考虑如何对所有的 k 求解

暴力求解是 O(kn) 的，卡了一年常没卡进去

幂函数是很烦的，考虑套路第二类斯特林数展开（证明可以参考这篇题解）

ans=\sum\limits_{v=1}^n f_v\sum\limits_{j=0}^kS_2(k,j)j!\tbinom{v}{j} =\sum\limits_{j=0}^kS_2(k,j)\sum\limits_{v=1}^n f_v\frac{v!}{(v-j)!}

后面明显是个差卷积，没学过可以写一下力

那么可以对所有的 j 计算出后面的值 x_j

则 ans=\sum\limits_{j=0}^kS_2(k,j)x_j

那么只需要知道第二类斯特林数就可以计算答案了

考虑斯特林数的组合意义， n 个球放入 m 个盒子，那么第 n 个可以和前面的一起或者新加一个盒子

那么 S_2(n,m)=S_2(n-1,m)\times m+S_2(n-1,m-1)

边界条件 S_2(n,0)=[n=0]

可以递推得到所有所需的第二类斯特林数。本题可能卡空间，可以滚动数组优化。

总复杂度 O(n\log n+k^2)

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
std::mt19937 rnd(time(0));
inline int sj(int n)
{
    unsigned int x=rnd();
    return x%n+1;
}
#define rand fst
template<typename typC> void read(register typC &x)
{
    register int c=getchar(),fh=1;
    while ((c<48)||(c>57))
    {
        if (c=='-') {c=getchar();fh=-1;break;}
        c=getchar();
    }
    x=c^48;c=getchar();
    while ((c>=48)&&(c<=57))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    x*=fh;
}
template<typename typC> void write(register typC x)
{
    if (x<0) putchar('-'),x=-x;
    static int st[100];
    register int tp=1,y;st[1]=x%10;x/=10;
    while (x) y=x/10,st[++tp]=x-y*10,x=y;++tp;
    while (--tp) putchar(st[tp]|48);
}
template<typename typC> void write(register typC *a,register int num)
{
    for (register int i=1;i<=num;i++) write(a[i]),putchar(i==num?10:32);
}
#define space(x) write(x),putchar(32)
#define enter(x) write(x),putchar(10)
const int N=262145<<1,p=998244353;
inline void inc(register int &x,const int y)
{
    if ((x+=y)>=p) x-=p;
}
inline void dec(register int &x,const int y)
{
    if ((x-=y)<0) x+=p;
}
inline int ksm(register int x,register int y)
{
    register int r=1;
    while (y)
    {
        if (y&1) r=(ll)r*x%p;
        x=(ll)x*x%p;y>>=1;
    }
    return r;
}
int a[N],b[N];
int f[N],ff[N],x[N],g[N],mi[N],r[N],yg[N],ig[N],inv[N],ifac[N],fac[N],s[2][5002];
int n,m,i,j,l,biglim,ans;
inline void ycl(int l,int limit)
{
    for (int i=1;i<limit;i++) r[i]=r[i>>1]>>1|(i&1)<<l;
}
inline void getg(int limit)
{
    ig[limit]=ksm(yg[limit]=ksm(3,(p-1)/limit),p-2);
    for (int i=limit>>1;i;i>>=1)
    {
        yg[i]=(ll)yg[i<<1]*yg[i<<1]%p;
        ig[i]=(ll)ig[i<<1]*ig[i<<1]%p;
    }
}
void dft(int *a,int xs,int limit)
{
    int i,j,k,l,w,wn,b,c;
    for (i=1;i<limit;i++) if (i<r[i]) swap(a[i],a[r[i]]);
    for (i=1;i<limit;i=l)
    {
        l=i<<1;
        if (xs) wn=yg[l]; else wn=ig[l];
        for (j=0;j<limit;j+=l)
        {
            w=1;
            for (k=0;k<i;k++,w=(ll)w*wn%p)
            {
                b=a[j|k];c=(ll)a[j|k|i]*w%p;
                a[j|k]=(b+c)%p;
                a[j|k|i]=(b+p-c)%p;
            }
        }
    }
    if (!xs)
    {
        xs=ksm(limit,p-2);
        for (i=0;i<limit;i++) a[i]=(ll)a[i]*xs%p; 
    }
}
inline void ginv(int n)
{
    inv[1]=ifac[0]=ifac[1]=1;
    for (int i=2;i<=n;i++) ifac[i]=(ll)ifac[i-1]*(inv[i]=p-(ll)p/i*inv[p%i]%p)%p;
}
inline void ji(int *a,int n)
{
    for (int i=n+1;i;i--) a[i]=(ll)a[i-1]*inv[i]%p;
    a[0]=1;
}
inline void dao(int *a,int n)
{
    for (int i=0;i<n;i++) a[i]=(ll)a[i+1]*(i+1)%p;
    a[n]=0;
}
void getinv(int *f,int *g,int biglim)
{
    int i,l=1,limit,j;
    g[0]=ksm(f[0],p-2);
    for (i=2;i<=biglim;i=limit,l++)
    {
        limit=i<<1;
        memcpy(x,f,limit<<1);
        ycl(l,limit);
        dft(x,1,limit);dft(g,1,limit);
        for (j=0;j<limit;j++) g[j]=(ll)g[j]*(2-(ll)g[j]*x[j]%p+p)%p;
        dft(g,0,limit);
        memset(g+i,0,limit<<1);
    }
}
inline int C(register int n,register int m)
{
    return (ll)fac[n]*ifac[m]%p*ifac[n-m]%p;
}
int main()
{
    read(n);read(m);
    if (n==1)
    {
        for (i=0;i<=m;i++) puts("1");return 0;
    }
    if (n==2)
    {
        puts("3");
        for (i=1;i<=m;i++) printf("%d\n",(1+ksm(ksm(2,p-2),i-1))%p);
        return 0;
    }
    fac[0]=1;
    for (i=1;i<=n;i++) fac[i]=(ll)fac[i-1]*i%p;
    ginv(n);
    for (i=0;i<=n;i++) f[i]=(ll)(ff[i]=ksm(2,((ll)i*(i-1)>>1)%(p-1)))*ifac[i]%p;
    biglim=1;
    while (biglim<=n) biglim<<=1;
    getg(biglim<<1);
    getinv(f,g,biglim);
    dao(f,n);
    biglim<<=1;
    dft(f,1,biglim);dft(g,1,biglim);
    for (i=0;i<biglim;i++) f[i]=(ll)f[i]*g[i]%p;
    dft(f,0,biglim);
    ji(f,n);
    for (i=1;i<=n;i++) f[i]=(ll)f[i]*fac[i]%p;
    for (i=1;i<=n;i++) f[i]=(ll)f[i]*ff[n-i]%p*C(n,i)%p*fac[i]%p;
    f[0]=0;memset(f+n+1,0,sizeof(f)-(n+1<<2));
    memset(g,0,sizeof(g));
    for (i=0;i<=n;i++) g[n-i]=f[i];
    memset(f,0,sizeof(f));
    for (i=0;i<=n;i++) f[i]=ifac[i];
    dft(f,1,biglim);dft(g,1,biglim);
    for (i=0;i<biglim;i++) f[i]=(ll)f[i]*g[i]%p;
    dft(f,0,biglim);
    memset(g,0,sizeof(g));
    for (i=0;i<=n;i++) g[n-i]=f[i];
    register int i,j;int nn=n,mm=m;
    register int n=nn,m=mm,ans=0,y;
    s[0][0]=1;
    for (j=0;j<=m;j++)
    {
        ans=0;y=j&1;
        for (i=0;i<=j;i++) ans=(ans+(ll)s[y][i]*g[i])%p;
        s[y^1][0]=0;++j;
        for (i=1;i<=j+1;i++) s[y^1][i]=((ll)s[y][i]*i+s[y][i-1])%p;
        --j;ans=(ll)ans*ksm(ksm(n,j),p-2)%p;printf("%d\n",ans);
    }
}