数据已修正！标程写错了- -
话说这题当场我切掉了来着，不过那里评测机太慢，给我卡掉了两个点，感觉很不爽，现在只能低空飞过，最慢的点0.9s+
欢迎诸位把我刷掉！

第一种方法是强行化简这个式子。
首先S(i,j)当j>i时是0，所以原式可写成$\sum_{i=0}^n\sum_{j=0}^nS(i,j)*2^j*j!$
再考虑如何求$S(n,m)*m!$，它的意义是n个不同的球，放进m个不同的盒子里，盒子不允许空的方案数，求它的通项有很多方法，这里介绍比较简便的生成函数求法。
我们固定m，并定义多项式$A(x)=\sum_{i=0}^\infty A_i\frac{x^n}{n!}$的每一项系数$A_i$表示$S(i,m)*m!$
那$A(x)=(e^x-1)^m$（想一想，为什么）。
于是$S(n,m)*m!$即$\frac{x^n}{n!}$的系数就是$\sum_{j=0}^n(-1)^kC_j^k(j-k)^i$
原式即变为$\sum_{i=0}^n\sum_{j=0}^n2^j\sum_{k=0}^j(-1)^kC_j^k(j-k)^i$
变形得$\sum_{j=0}^n2^j*j!\sum_{k=0}^j\frac{(-1)^k}{k!}*\frac{\sum_{i=0}^n\;(j-k)^i}{(j-k)!}$
定义多项式$F(x)$的每一项$F_i=\frac{(-1)^i}{i!}$，定义多项式$G(x)$的每一项$G_i=\frac{\sum_{j=0}^ni^j}{i!}$，定义多项式$H(x)=F(x)*G(x)$
则$ans=\sum_{j=0}^n2^j*j!*H_j$
NTT一发就行了。
第二种方法是考虑原式的意义。
$F_i=\sum_{j=0}^iS(i,j)*2^j*j!$的意义是把n个不同的球，放进若干个不同的盒子了，盒子不允许空，每个盒子有两种状态的方案数。
枚举最后一个盒子的球数可得递推式$F_i=\sum_{j=1}^i2C_i^jF_{i-j}$
变形得$\frac{F_i}{i!}=\sum_{j=1}^i\frac 2{j!}*\frac{F_{i-j}}{(i-j)!}$
这是个卷积的形式，多项式求逆或者分治搞一搞就行了。

当初输出序列最大数过了这道题，现在终于会正解了！
%ysf

注意到$0^0=1$

嗯，对动态规划的理解更深了

写记忆化搜索
一个>=写成了>
WA了一个点

题目配的图好丑。。
整体二分(id=373672)实力碾压树状数组套主席树(id=373424)，不过在我发这个评论的时候分别是榜前二，希望不会被dalao们踩的太惨。。

数据可能真的有点弱 没有在最前面插入0 也过了

回复 @安呐一条小咸��。 :
%

回复 @安呐一条小咸��。 :
……

我连Djs都不会写了,我和咸鱼没区别。

滑稽♂树上滑稽♂果

= =随机化太玄学了，60 -> 90 -> 100。莫名其妙rk1

没算好数组大小 身败名裂...

1A我真是感动

说明：时限给的是造数据用的程序用时的2倍。
内存也是算的差不多的。。。
不过cogs的内存用量的计算计算造数据用程序只用了1m多内存真是让人一脸萌币

身败名裂……