题目链接

\(Description\)

求$$\sum_{i=0}^n\sum_{j=0}iS(i,j)\times 2^j\times j!\mod 998244353$$

其中\(S(i,j)\)为第二类斯特林数（\(S(n,m)\)即在\(m\)个无区别盒子中放\(n\)个不同小球的方案数）。

\(Solution\)

（不知博客园markdowm怎么回事就是显示格式错误）

另：第二类斯特林数 总结。

//7988kb	2340ms

#include <cstdio>

#include <algorithm>

#define mod 998244353

#define G 3

#define invG 332748118

#define Mod(x) x>=mod&&(x-=mod)

typedef long long LL;

const int N=(1<<18)+5;

int pw[N],fac[N],ifac[N],inv[N],rev[N],f[N],g[N];

inline int FP(int x,int k)

{

	int t=1;

	for(; k; k>>=1,x=1ll*x*x%mod)

		if(k&1) t=1ll*t*x%mod;

	return t;

}

void NTT(int *a,int lim,int type)

{

	for(int i=1; i<lim; ++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);

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

	{

		int mid=i>>1;

		int Wn=FP(~type?G:invG,(mod-1)/i);

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

		{

			int w=1,t;

			for(int k=0; k<mid; ++k,w=1ll*w*Wn%mod)

				a[j+k+mid]=(a[j+k]-(t=1ll*a[j+k+mid]*w%mod)+mod), Mod(a[j+k+mid]),

				a[j+k]+=t, Mod(a[j+k]);

		}

	}

	if(type==-1) for(int i=0,inv=FP(lim,mod-2); i<lim; ++i) a[i]=1ll*a[i]*inv%mod;

}

int main()

{

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

	pw[0]=fac[0]=1;

	for(int i=1; i<=n; ++i)

		pw[i]=pw[i-1]<<1, Mod(pw[i]), fac[i]=1ll*fac[i-1]*i%mod;

	ifac[n]=FP(fac[n],mod-2);

	for(int i=n-1; ~i; --i) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;

	inv[1]=1;

	for(int i=2; i<=n; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

	f[0]=g[0]=1, f[1]=mod-1/*not -1==*/, g[1]=n+1;

	for(int i=2; i<=n; ++i)

		f[i]=i&1?(mod-ifac[i]):ifac[i],

		g[i]=1ll*(FP(i,n+1)-1)*inv[i-1]%mod*ifac[i]%mod;//FP(..,..)!=0

	int len=-1,lim=1; while(lim<=n<<1) lim<<=1,++len;

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

	NTT(f,lim,1), NTT(g,lim,1);

	for(int i=0; i<lim; ++i) f[i]=1ll*f[i]*g[i]%mod;

	NTT(f,lim,-1);

	LL ans=0;

	for(int i=0; i<=n; ++i) ans+=1ll*pw[i]*fac[i]%mod*f[i]%mod;

	printf("%lld\n",ans%mod);

	return 0;

}

自留

### $Description$

求$$\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times j!\mod 998244353$$

其中$S(i,j)$为第二类斯特林数（$S(n,m)$即在$m$个无区别盒子中放$n$个不同小球的方案数）。

### $Solution$

注意到$i<j$时，$S(i,j)=0$，所以$j$的上界可以到$n$。

$$\begin{aligned}\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times j!&=\sum_{i=0}^n\sum_{j=0}^nS(i,j)\times 2^j\times j!\\&=\sum_{j=0}^n2^j\cdot j!\cdot\sum_{i=0}^nS(i,j)\tag !\end{aligned}$$

$S(n,m)$的一个公式为$$S(n,m)=\frac{1}{m!}\sum_{k=0}^m(-1)^kC(m,k)(m-k)^n$$

即利用容斥，枚举强制为空的盒子有多少个（空盒子至少有多少个）。因为盒子无序所以再除以$m!$。然后可以化简。$$\begin{aligned}S(n,m)&=\frac{1}{m!}\sum_{k=0}^m(-1)^kC(m,k)(m-k)^n\\&=\sum_{k=0}^m(-1)^k\frac{1}{k!(m-k)!}(m-k)^n\\&=\sum_{k=1}^m\frac{(-1)^k}{k!}\cdot\frac{(m-k)^n}{(m-k)!}\end{aligned}$$

注意到这是个卷积形式，所以我们可以$O(n\log n)$计算出$S(n,i)$。

当然本题还是把上式代回去。$$\begin{aligned}\sum_{j=0}^n2^j\cdot j!\cdot\sum_{i=0}^nS(i,j)&=\sum_{j=0}^n2^j\cdot j!\cdot\sum_{i=0}^n\sum_{k=0}^j\frac{(-1)^k}{k!}\cdot\frac{(j-k)^i}{(j-k)!}\\&=\sum_{j=0}^n2^j\cdot j!\cdot\sum_{k=0}^j\frac{(-1)^k}{k!}\cdot\frac{\sum_{i=0}^n(j-k)^i}{(j-k)!}\tag !\end{aligned}$$

注意到后面还是个卷积形式，令$f(x)=\frac{(-1)^x}{x!},g(x)=\frac{\sum_{i=0}^nx^i}{x!}$。

设$S_n=\sum_{i=0}^nx^i$，则$xS_n=\sum_{i=1}^{n+1}x^i$，得$S_n=\frac{x^{n+1}-1}{x-1}$，即$g(x)=\frac{x^{n+1}-1}{(x-1)x!}\tag !$。特殊的，令$g(0)=1,g(1)=n+1$。

这样$f,g$都可以递推。

然后$$Ans=\sum_{j=0}^n2^j\cdot j!\cdot(f*g)(j)$$

NTT就行了。