第二类斯特林数

斯特林数

讲道理，斯特林数分为两类，递推式子类似组合数，分别是$S(i,j)=S(i-1,j-1)+S(i-1,j)\times (i-1),S(i,j)=S(i-1,j-1)+j\times S(i-1,j)$

（因为我不知道第一类有啥用，所有就直接上第二类...

第二类斯特林数

对于上述表达式，是有意义的（废话，不然我不会讲

这个东西，其实表达的东西很巧妙，就是：把n个不同的小球放在m个相同的盒子里方案数。

记住上面的东西，这个是定义！这个是定义！这个是定义！

根据上述的定义可以得到容斥原理的式子

$S(n,m)={\frac 1 {m!}}\sum_{k=0}^m (-1)^k C(m,k)(m-k)^n$

道理是这样的，枚举空盒的个数，这样就可以容斥出恰好为$K$的方案数...

然后同样，通过定义可以知道，$x^k=\sum\limits_{j=0}^kS(k,j)\times j!\times C(x,j)$

同样，是表示，枚举空盒数量，剩下来的划分的方案数，这个东西显然是给你$K$个球随便放不用的方案数...

上面的那个东西很重要，真的很重要！

因为可以把$x^k$转化为$C(x,j)$，这样就可以用$C(x,j)=C(x-1,j-1)+C(x-1,j)$的性质了...

这类斯特林数显然可以通过推式子转化为卷积形式（自己推吧...

那么可以开始例题时间了...

例题时间

这个东西就用到上面的性质了！

然后式子长成这个样子：$ans=n\times 2^{C(n-1,2)}\sum\limits_{i=0}^{n-1}i^k C(n-1,i)$

然后显然，就需要把$i^k$替换一下，$ans=n\times 2^{C(n-1,2)}\sum\limits_{i=0}^{n-1}C(n-1,i)\sum\limits_{j=0}^kS(k,j)\times j!\times C(i,j)$

设：$f(n,m)=\sum\limits_{i=0}^{n-1}C(n,i)\sum\limits_{j=0}^mS(m,j)\times j!\times C(i,j)$

那么：$f(n,m)=\sum\limits_{j=0}^mj!\times S(m,j)\sum\limits_{i=0}^{n}C(n,i)C(i,j)$

根据定义展开组合数：$f(n,m)=\sum\limits_{j=0}^mj!\times S(m,j)\times C(n,j)\times 2^{n-j}$，显然，因为后面的东西表示的是先在$n$个数中选$i$个然后再选$j$个的方案数，这个东西就等于再$n$个数中选$j$个，剩下$n-j$选不选都行的方案数...

这个东西显然可以算了...

只需要快速求出$S(m,j)$，这个东西你自己推去，我才不写呢...

代码.jpg

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 262205#define ll long long#define mod 998244353int fac[N],inv[N],n,k,A[N<<1],B[N<<1];int q_pow(int x,int n){int ret=1;for(;n;n>>=1,x=(ll)x*x%mod)if(n&1)ret=(ll)ret*x%mod;return ret;}int q_pow(int x,ll n){int ret=1;for(;n;n>>=1,x=(ll)x*x%mod)if(n&1)ret=(ll)ret*x%mod;return ret;}#define inv(x) q_pow(x,mod-2)void NTT(int *a,int len,int flag){ int i,j,k,t,w,x,tmp; for(i=k=0;i
            
             k)swap(a[i],a[k]); for(j=len>>1;(k^=j)
             
              >=1); } for(k=2;k<=len;k<<=1) { x=q_pow(3,(mod-1)/k);if(flag==-1)x=inv(x);t=k>>1; for(i=0;i
             
            
           
          
         
        
       
      
     
    

这个题非常有趣...

同样利用$x^k=\sum\limits_{j=0}^kS(k,j)\times j! \times C(x,j)$的性质...

显然可以讲所以的$dis$转化为子树内和子树外。

那么，设：$f(x)$表示$x$的子树内贡献，$g(x)$为$x$的子树外贡献。

对应$(f(x))^k=\sum (f(to)+1)^k$

对应$(g(x))^k=(f(fa)+1)^k+(g(fa)+1)^k-(f(x)+2)^k$

之间暴力二项式大概需要跑100s左右。

然后可以用斯特林数展开，发现前两者之间组合数加法就行，最后的那个需要展开两次...

代码.jpg

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 50005#define M 155#define mod 10007#define ll long longstruct node{int to,next;}e[N<<1];int s[M][M],f[N][M],g[N][M],n,K,head[N],cnt,siz[N],fac[M];inline void add(int x,int y){e[cnt]=(node){y,head[x]};head[x]=cnt++;}void dfs1(int x,int from){ siz[x]=1;f[x][0]=1; for(int i=head[x];i!=-1;i=e[i].next) { int to1=e[i].to; if(to1!=from) { dfs1(to1,x);f[x][0]=(f[x][0]+f[to1][0])%mod;int lim=min(siz[x],K); for(int j=1;j<=K;j++)f[x][j]=(f[x][j]+f[to1][j-1]+f[to1][j])%mod; siz[x]+=siz[to1]; } }}void dfs2(int x,int from){ for(int i=head[x];i!=-1;i=e[i].next) { int to1=e[i].to; if(to1!=from) { g[to1][0]=n-f[to1][0]; for(int j=1;j<=K;j++) { g[to1][j]=((g[x][j]+g[x][j-1]+f[x][j-1]+f[x][j]-f[to1][j]-(f[to1][j-1]<<1))%mod+mod)%mod; if(j>1)g[to1][j]=(g[to1][j]-f[to1][j-2]+mod)%mod; } dfs2(to1,x); } }}int main(){ int L,A,B,Q,now;memset(head,-1,sizeof(head)); scanf("%d%d%d%d%d%d%d",&n,&K,&L,&now,&A,&B,&Q); for(int i=1,x;i