「Luogu4091」[HEOI2016/TJOI2016]求和

problem

Solution

我们知道当\(i时，\(S(i,j)=0\)，所以

\[\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times j! \]

\[=\sum_{j=0}^n2^j\times j!\sum_{i=0}^nS(i,j) \]

将第二类斯特林数的展开式代入得

\[\sum_{j=0}^n2^j\times j!\sum_{i=0}^n\frac{1}{j!}\sum_{k=0}^j(-1)^k\times\begin{pmatrix}j\\k\end{pmatrix}(j-k)^i \]

\[=\sum_{j=0}^n2^j\times j!\sum_{i=0}^n\sum_{k=0}^j\frac{(-1)^k}{k!}\times\frac{(j-k)^i}{(j-k)!} \]

\[=\sum_{j=0}^n2^j\times j!\sum_{k=0}^j\frac{(-1)^k}{k!}\times\frac{\sum_{i=0}^n(j-k)^i}{(j-k)!} \]

\[=\sum_{j=0}^n2^j\times j!\sum_{k=0}^j\frac{(-1)^k}{k!}\times\frac{(j-k)^{n+1}-1}{(j-k-1)(j-k)!} \]

后面那玩意看起来很像两个函数的卷积

我们令\(f(x)=\frac{(-1)^x}{x!},g(x)=\frac{x^{n+1}-1}{(x-1)x!}\)

代入得

\[\sum_{j=0}^n2^j\times j!\sum_{k=0}^jf(k)\times g(j-k) \]

\[=\sum_{j=0}^n2^j\times j!(f*g)(j) \]

然后就可以用\(NTT\)来预处理出\((f*g)\)了

Code

#include 
#include 
#include 
#include 
#include 
#include 
#define inv(x) ((fastpow((x),mod-2)))
using namespace std;
typedef long long ll;

template void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const ll mod=998244353,gg=3,ig=332748118;
const int maxn=100000+5;
int n;
ll f[maxn<<3],g[maxn<<3];
int len;
int rev[maxn<<3];

ll fastpow(ll a,ll b)
{
	ll re=1,base=a;
	while(b)
	{
		if(b&1)
			re=re*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return re;
}

void NTT(ll *f,int type)
{
    for(register int i=0;i>1;
        ll unr=fastpow(type==1?gg:ig,(mod-1)/p);
        for(register int l=0;l>1]>>1)|((i&1)?len>>1:0));
	NTT(f,1);
	NTT(g,1);
	for(register int i=0;i