题目

关于斯特林数与反演的更多姿势\(\Longrightarrow\)

做法

\[\begin{aligned}\\ Ans&=\sum\limits_{i=0}^n \sum\limits_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix}2^j×j!~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1\\ &=\sum\limits_{i=0}^n \sum\limits_{j=0}^n \begin{Bmatrix}i\\j\end{Bmatrix}2^j×j!~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~2\\ &=\sum\limits_{j=0}^n 2^j×j!\sum\limits_{i=0}^n \begin{Bmatrix}i\\j\end{Bmatrix}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~3\\ &=\sum\limits_{j=0}^n 2^j×j!\sum\limits_{i=0}^n \sum\limits_{k=0}^j\frac{(-1)^k}{k!}\cdot\frac{(j-k)^i}{(j-k)!}~~~~~~~~~~~~~~~~~~~~4\\ &=\sum\limits_{j=0}^n 2^j×j!\sum\limits_{k=0}^j\frac{(-1)^k}{k!}\cdot\frac{ \sum\limits_{i=0}^n (j-k)^i}{(j-k)!}~~~~~~~~~~~~~~~~~~~~~~5\\ &=\sum\limits_{j=0}^n 2^j×j!\sum\limits_{k=0}^j\frac{(-1)^k}{k!}\cdot \frac{(j-k)^{n+1}-1}{(j-k-1)(j-k)!}~~~~~~~6\\ \end{aligned}\]

• \(2：\begin{Bmatrix}i\\j\end{Bmatrix}=0(i>j)\)
• \(3：\)移项
• \(4：\)
• \(5：\)移项化卷积
• \(6：\)等比公式

总结

这题非常有意思，最后一步对于蒟蒻来说还是少见的，推到\(4\)谁都会，然后就无从下手了

以至于会从头考虑\(2^j×j!\)的性质，特别容易想偏

Code

#include
    
     typedef int LL;typedef long long L;const LL maxn=3e5+9,mod=998244353,g=3,_g=332748118;inline LL Pow(LL base,LL b){    LL ret(1);    while(b){        if(b&1) ret=(L)ret*base%mod; base=(L)base*base%mod; b>>=1;    }return ret;}LL fac[maxn],fav[maxn],r[maxn],F[maxn],G[maxn],W[maxn];inline void NTT(LL *a,LL n,LL type){    for(LL i=0;i
     
      =mod) a[j+k]%=mod;                a[j+mid+k]=x-y; if(a[j+mid+k]<0) a[j+mid+k]+=mod;            }    }}inline LL Fir(LL n){    LL limit(1),len(0);    while(limit
      
       >1]>>1)|((i&1)<
       
        =1;--i) fav[i-1]=(L)fav[i]*i%mod;        printf("%d",Solve_fg(n));    return 0;}