博主曾更过一篇复杂度为$O( k· log k)$的多项式做法在这里
惊闻本题有$ O(k)$的神仙做法，说起神仙我就想起了于是就去学习了一波
幂与第二类斯特林数
$$ x^k=sum_{j=0}^kj!inom{x}{j}egin{Bmatrix}k\jend{Bmatrix}$$
$$ egin{Bmatrix}k\jend{Bmatrix}=frac{1}{j!}sum_{i=0}^ji^kinom{j}{i}(-1)^{j-i}$$
以上是两个非常实用的公式
推式子
现在开始推式子
原博文已经推出了我们真正需要求的是$ f(n,k)=sumlimits_{i=0}^ninom{n}{i}i^k$
根据上面的公式可以推得
$$
egin{aligned}
f(n,k) & =sum_{i=0}^ninom{n}{i}i^k=sum_{j=0}egin{Bmatrix}k\jend{Bmatrix}frac{n!}{(n-j)!}2^{n-j}\
& =sum_{j=0}^kfrac{n!}{(n-j)!}2^{n-j}frac{1}{j!}sum_{i=0}^j(-1)^{j-i}inom{j}{i}i^k\
&=sum_{j=0}^kinom{n}{j}2^{n-j}sum_{i=0}^j(-1)^{j-i}inom{j}{i}i^k\
&=sum_{i=0}^kinom{n}{i}i^ksum_{j=i}^k2^{n-j}(-1)^{j-i}inom{n-i}{j-i}\
&=sum_{i=0}^kinom{n}{i}i^k2^{n-i}sum_{j=0}^{k-i}inom{n-i}{j}(-frac{1}{2})^j
end{aligned}
$$
我们需要快速递推出$A(i)=displaystylesum_{j=0}^{k-i}inom{n-i}{j}(-frac{1}{2})^j$
再推波式子得
$$
egin{aligned}
sum_{j=0}^{k-i}inom{n-i}{j}(-frac{1}{2})^j&=sum_{j=0}^{k-i}left(inom{n-i-1}{j}+inom{n-i-1}{j-1}
ight)(-frac{1}{2})^j\
&=sum_{j=1}^{k-i}(-frac{1}{2})^jinom{n-i-1}{j-1}+sum_{j=0}^{k-i}(-frac{1}{2})^jinom{n-i-1}{j}\
&=-frac{1}{2}sum_{j=0}^{k-i-1}(-frac{1}{2})^jinom{n-i-1}{j}+sum_{j=0}^{k-i}(-frac{1}{2})^jinom{n-i-1}{j}\
&=frac{1}{2}sum_{j=0}^{k-i-1}(-frac{1}{2})^jinom{n-i-1}{j}+(-frac{1}{2})^{k-i}inom{n-i-1}{k-i}
end{aligned}
$$
因此$A(i)=frac{1}{2}A(i+1)+(-frac{1}{2})^{k-i}inom{n-i-1}{k-i}$
就假装推完了
大常数代码
#include<ctime> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define p 998244353 #define inv2 499122177 #define rt register int #define ll long long using namespace std; inline ll read(){ ll x = 0; char zf = 1; char ch = getchar(); while (ch != '-' && !isdigit(ch)) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf; } void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);} void writeln(const ll y){write(y);putchar(' ');} int i,j,k,m,n,x,y,z,cnt; int ksm(int x,int y=p-2){ int ans=1; for(rt i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p; return ans; } int inv[500010],A[500010]; int v[500010],ss[500010];bool b[500010]; int main(){ n=read()-1;k=read(); inv[0]=inv[1]=1; v[1]=1;v[0]=(k==0); for(rt i=2;i<=k;i++){ if(!b[i])ss[++cnt]=i,v[i]=ksm(i,k); for(rt j=1;i*ss[j]<=k&&j<=cnt;j++){ b[i*ss[j]]=1;v[i*ss[j]]=1ll*v[i]*v[ss[j]]%p; if(i%ss[j]==0)break; } } for(rt i=2;i<=k;i++)inv[i]=1ll*inv[p%i]*(p-p/i)%p; int ans=0; if(n<=k){ for(rt i=0,c=1;i<=n;c=1ll*(n-i)*inv[i+1]%p,i++) ans+=1ll*c*v[i]%p; cout<<(1ll*ans*(n+1)%p*ksm(2,(ll)n*(n-1)/2%(p-1))%p+p)%p; return 0; } A[k]=1; for(rt i=k-1,y=-inv2,c=n-i-1;i>=0;i--,y=1ll*y*-inv2%p){ A[i]=(1ll*A[i+1]*inv2%p+1ll*c*y%p)%p; c=1ll*c*(n-i)%p*inv[k-i+1]%p; } for(rt i=0,d=ksm(2,n),c=1;i<=k&&i<=n;c=1ll*c*(n-i)%p*inv[i+1]%p,i++,d=1ll*d*inv2%p) (ans+=1ll*c*v[i]%p*d%p*A[i]%p)%=p; cout<<(1ll*ans*(n+1)%p*ksm(2,(ll)n*(n-1)/2%(p-1))%p+p)%p; return 0; }