$\begin{aligned}\sum\limits_{i=0}^n\sum\limits_{j=0}^i S(i,j)\times(j!)\times 2^j&=\sum\limits_{i=0}^n\sum\limits_{j=0}^n2^j\sum\limits_{k=0}^n (-1)^{j-k}\tbinom{j}{k}k^i\\&=\sum\limits_{i=0}^n\sum\limits_{j=0}^n(-2)^j\sum\limits_{k=0}^j (-1)^k\tbinom{j}{k}k^i\\&=\sum\limits_{k=0}^nf(k)(-1)^k\sum\limits_{j=0}^{n}\tbinom{j}{k}(-2)^j \end{aligned}$
其中,$f(k)=\sum_{i=0}^n k^i$
就是这一坨$\sum\limits_{j=0}^{n}\tbinom{j}{k}(-2)^j$,不好求。
运用有限微积分公式$\sum u\Delta v=uv-\sum Ev\Delta u$,
设$\Delta v=(-2)^j,u=\tbinom{j}{k}$,可以很轻松地得到:
$\Delta u=\tbinom{j+1}{k}-\tbinom{j}{k}=\tbinom{j}{k-1},v=\frac{(-2)^j}{-3}$
于是乎,
$\begin{aligned}\sum\limits_{j=0}^{n}\tbinom{j}{k}(-2)^j&=\sum\limits_{j=0}^{n+1}\tbinom{j}{k}(-2)^j\delta j\\&=[\frac{(-2)^j}{-3}\tbinom{j}{k}]|^{n+1}_{0}-\sum\limits_{j=0}^{n+1}\tbinom{j}{k-1}\frac{(-2)^{j+1}}{-3}\delta j\\&=[\frac{(-2)^j}{-3}\tbinom{j}{k}]|^{n+1}_{0}-\frac{-2}{-3}\sum\limits_{j=0}^{n+1}\tbinom{j}{k-1}(-2)^{j}\delta j\end{aligned}$
当$k=0$时,为
$[\frac{(-2)^j}{-3}\tbinom{j}{0}]|^{n+1}_{0}=\frac{(-2)^{n+1}}{-3}-\frac{1}{-3}$
当$k=1$时,
为$[\frac{(-2)^j}{-3}\tbinom{j}{1}]|^{n+1}_{0}-\frac{2}{3}[\frac{(-2)^j}{-3}\tbinom{j}{0}]|^{n+1}_{0}=[(n+1)\frac{(-2)^{n+1}}{-3}]-\frac{2}{3}[\frac{(-2)^{n+1}}{-3}-\frac{1}{-3}]$
当$k=2$时,
为$[\frac{(n+1)n}{2}\frac{(-2)^{n+1}}{-3}]-\frac{2}{3}\{[(n+1)\frac{(-2)^{n+1}}{-3}]-\frac{2}{3}[\frac{(-2)^{n+1}}{-3}-\frac{1}{-3}]\}$
发现可以递推。
$f(k)$可以转化为$\frac{k^{n+1}-1}{k-1}$线性求得。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int mod=998244353,N=1e5+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
inline int ksm(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;}
int pn[N],prime[N],inv[N],n,m;bool v[N];
void gp()
{
inv[0]=1;inv[1]=1;m=0;pn[1]=1;
for(int i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
for(int i=2;i<=n;i++)
{
if(!v[i])prime[++m]=i,pn[i]=ksm(i,n+1);
for(int j=1;j<=m&&1ll*i*prime[j]<=n;j++)
{
v[i*prime[j]]=1;pn[i*prime[j]]=1ll*pn[i]*pn[prime[j]]%mod;
if(i%prime[j]==0)break;
}
}
}
int main()
{
qr(n);if(n==1){puts("1");return 0;}
gp();
int t1=-1ll*ksm(-2,n+1)*inv[3]%mod,t2=-2*inv[3]%mod;
int f0=-inv[3],fn=t1,ans=(fn-f0)%mod,bin=n+1;
f0=1ll*t2*f0%mod,fn=(1ll*t1*(n+1)+1ll*t2*fn)%mod;
ans=(ans-1ll*(n+1)*(fn-f0))%mod;
for(int i=2;i<=n;i++)
{
bin=1ll*bin*(n+2-i)%mod*inv[i]%mod,f0=1ll*t2*f0%mod,fn=(1ll*t1*bin+1ll*t2*fn)%mod;
ans=(ans+((i&1)?-1:1)*(1ll*inv[i-1]*(pn[i]-1)%mod*(fn-f0)))%mod;
}
qw((ans+mod)%mod);puts("");
return 0;
}
0 条评论