【题解】幼儿园篮球题(范德蒙德卷积+斯特林+NTT)

【题解】幼儿园篮球题(NTT+范德蒙德卷积+斯特林数)

题目就是要我们求一个式子(听说叫做超几何分布？好牛逼的名字啊)

\[\sum_{i=1}^{S}\dfrac 1 {N \choose n_i}\sum_{j=0}^{k_i}{m_i \choose j}{n_i-m_i\choose k_i- j}j^L
\]

实际上$S $很小，所以本质上就是求

\[\sum_{j=0}^{k_i}{m_i \choose j}{n_i-m_i\choose k_i- j}j^L
\]

为了方便我写成这个形式

\[\sum_{j=0}^{k}{m \choose j}{n-m\choose k-j}j^L
\]

斯特林数划开次方

\[\sum_{j=0}^{k}{m \choose j}{n-m\choose k-j}\sum_{i=0}^{\min\{j,L\}}{L \brace i}{j \choose i}i!
\]

交换和式

\[\sum_{i=0}^{\min \{k,L\}}{L \brace i}i!\sum_{j=0}^{\min\{k,L\}}{j \choose i}{m\choose j}{n-m\choose k-j}
\]

备胎模型提一下

\[\sum_{i=0}^{\min \{k,L\}}{L \brace i}i!{m \choose i}\sum_{j=0}^{\min\{k,L\}}{m-i\choose j-i} {n-m\choose k-j}
\]

根据黑白模型，提出来(这个还有一个名字叫做范德蒙德卷积)

\[\sum_{i=0}^{\min \{k,L\}}{L \brace i}i!{m \choose i}{n-i\choose k-i}
\]

而$L \le 2\times 10^5$

回顾一下求斯特林数

\[{L\brace i}=\dfrac 1{i!}\sum_{j=0}^{i-1}(-1)^{j}{i\choose j}(i-j)^{L}
\]

NTT预处理就好了

仍然不想写代码...什么时候想了就贴一下

upd：补锅

//@winlere

#include<iostream>

#include<cstdio>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

namespace poly{

      const int maxn=1<<19|1;

      int r[maxn];

      inline void getr(const int&len){

	    static int sav=0;

	    if(len==sav) return;

	    int cnt=0;

	    for(register int t=1;t<len;t<<=1)++cnt;

	    for(register int t=0;t<len;++t) r[t]=r[t>>1]>>1|(t&1)<<cnt>>1;

      }

      const int mod=998244353;

      const int g=3;

      inline int ksm(const int&base,const int&p){

	    register int ret=1;

	    for(register int t=p,b=base%mod;t;t>>=1,b=1ll*b*b%mod)

		  if(t&1) ret=1ll*b*ret%mod;

	    return ret;

      }

      const int gi=ksm(3,mod-2);

      inline void NTT(int*a,const int&len,const int&tag){

	    int*a0,*a1,s=g;

	    if(tag!=1) s=gi;

	    getr(len);

	    for(register int t=0;t<len;++t) if(t<r[t])swap(a[t],a[r[t]]);

	    for(register int t=1,wn;t<len;t<<=1){

		  wn=ksm(s,(mod-1)/(t<<1));

		  for(register int i=0;i<len;i+=t<<1){

			a1=(a0=a+i)+t;

			for(register int k=0,w=1,m;k<t;++k,++a1,++a0,w=1ll*w*wn%mod){

			      m=1ll**a1*w%mod;

			      *a1=(*a0+mod-m)%mod;

			      *a0=(*a0+m)%mod;

			}

		  }

	    }

	    if(tag!=1) for(register int t=0,w=ksm(len,mod-2);t<len;++t) a[t]=1ll*a[t]*w%mod;

      }

}

using namespace poly;

const int maxn2=2e7+3;

int s[maxn],t1[maxn],t2[maxn];

int jc[maxn2],inv[maxn2];

int n,m,S,L;

inline void pre(const int&n){

      jc[0]=inv[0]=1;

      for(register int t=1;t<=n;++t) jc[t]=1ll*jc[t-1]*t%mod;

      inv[n]=ksm(jc[n],mod-2);

      for(register int t=n-1;t;--t) inv[t]=1ll*inv[t+1]*(t+1)%mod;

      for(register int t=0;t<=L;++t) {

	    t1[t]=inv[t];

	    if(t&1) t1[t]=mod-t1[t];

	    t2[t]=1ll*inv[t]*ksm(t,L)%mod;

      }

      int k=1;

      while(k<=L)k<<=1;

      NTT(t1,k<<1,1);

      NTT(t2,k<<1,1);

      for(register int t=0,ed=k<<1;t<ed;++t)s[t]=1ll*t1[t]*t2[t]%mod;

      NTT(s,k<<1,-1);

      for(register int t=L+1;t<k<<1;++t) s[t]=0;

}

inline int c(const int&n,const int&m){

      if(n<m)return 0;

      return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;

}

inline int getans(const int&nn,const int&mm,const int&kk){

      int ret=0;

      for(register int t=0,ed=min(min(L,kk),min(nn,mm));t<=ed;++t)

	    ret=(ret+1ll*s[t]*inv[mm-t]%mod*jc[nn-t]%mod*inv[kk-t]%mod)%mod;

      return 1ll*ret*inv[nn]%mod*jc[mm]%mod*jc[kk]%mod;

}

int main(){

      n=qr();m=qr();S=qr();L=qr();

      pre(max(max(L,m),n));

      for(register int t=1,t1,t2,t3;t<=S;++t){

	    t1=qr();t2=qr();t3=qr();

	    printf("%d\n",getans(t1,t2,t3));

      }

      return 0;

}

巴特西

【题解】幼儿园篮球题(范德蒙德卷积+斯特林+NTT)

【题解】幼儿园篮球题(NTT+范德蒙德卷积+斯特林数)

最新文章

热门文章