题解 P7265 【Look At The Sky】
SSerxhs
2021-01-10 20:42:28
套路二合一
$n^kans=\sum\limits_{G}\sum\limits_{v\in G} v^k$
$=\sum\limits_{v=1}^n v^kf_v$
$f_v$ 表示数量 $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}}$
$g_v$ 是[城市规划](https://www.luogu.com.cn/problem/P4841)问题，没做过建议先写这题
于是我们 $O(n\log n)$ 计算出所有 $f_v$
接下来考虑如何对所有的 $k$ 求解
暴力求解是 $O(kn)$ 的，卡了一年常没卡进去
幂函数是很烦的，考虑套路第二类斯特林数展开（证明可以参考[这篇题解](https://www.luogu.com.cn/blog/SSerxhs/solution-p2791)）
$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)!}$
后面明显是个差卷积，没学过可以写一下[力](https://www.luogu.com.cn/problem/P3338)
那么可以对所有的 $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)$
```cpp
#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);
}
}
```