洛谷 P2791 幼儿园篮球题

---

我喜欢唱♂跳♂rap♂篮球

要求的是：\(\sum_{i=0}^kC_m^iC_{n-m}^{k-i}i^L\)

这个\(i^L\)很烦，就把第二类斯特林数的式子套进去

\(\sum_{i=0}^kC_m^iC_{n-m}^{k-i}i^L\)

\(\sum_{i=0}^kC_m^iC_{n-m}^{k-i}\sum_{j=0}^iC_{i}^j\begin{Bmatrix}L\\j\end{Bmatrix}j!\)

\(\sum_{j=0}^k\begin{Bmatrix}L\\j\end{Bmatrix}j!\sum_{i=j}^kC_m^iC_{n-m}^{k-i}C_{i}^j\)

后面\(\sum\)三个组合数好像很不好搞，但是\(C_{m}^{i}C_{i}^{j}=C_{m}^{j}C_{m-j}^{i-j}\)，可以拆出一个与\(i\)无关的组合数

\(\sum_{j=0}^k\begin{Bmatrix}L\\j\end{Bmatrix}j!C_{m}^{j}\sum_{i=j}^kC_{m-j}^{i-j}C_{n-m}^{k-i}\)

把式子化的好看一点，发现可以套范德蒙德卷积（\(\sum_{i=0}^kC_{n}^{i}C_{m}^{k-i}=C_{n+m}^k\)）

\(\sum_{j=0}^k\begin{Bmatrix}L\\j\end{Bmatrix}j!C_{m}^{j}\sum_{i=0}^kC_{m-j}^{k-i-j}C_{n-m}^{i}\)

\(\sum_{j=0}^k\begin{Bmatrix}L\\j\end{Bmatrix}j!C_{m}^{j}C_{n-j}^{k-j}\)

注意上面循环\(i\)的上界实际上是\(\min(k,L,m)=O(L)\)

求出\(n=L\)的一行第二类斯特林数，每次询问就可以\(O(L)\)了

把组合数全拆出来约分就洛谷rk1了= =

#include
    
     #define il inline#define vd void#define mod 998244353#define poly std::vector
     
      typedef long long ll;il ll gi(){    ll x=0,f=1;    char ch=getchar();    while(!isdigit(ch))f^=ch=='-',ch=getchar();    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return f?x:-x;}il int pow(int x,int y){    int ret=1;    while(y){        if(y&1)ret=1ll*ret*x%mod;        x=1ll*x*x%mod;y>>=1;    }    return ret;}#define maxn 524289poly pA,pB;int rev[maxn],_lstN,P[maxn],iP[maxn];il vd ntt(int*A,int N,int t){    for(int i=0;i
      
       i)std::swap(A[i],A[rev[i]]);    for(int o=1;o
       
        <<=1){        int W=t?P[o]:iP[o];        for(int*p=A;p!=A+N;p+=o<<1)            for(int i=0,w=1;i
        
         >1]>>1)|((i&1)<
         
          >1; poly _a(m); for(int i=0;i
          
           >1; poly _a(m); for(int i=0;i
           
            >1; poly _a(m); for(int i=0;i
            
             >1);}il vd poly_init(){ int G=3,iG=332748118; for(int i=1;i
             
              <<=1)P[i]=pow(G,(mod-1)/(i<<1)),iP[i]=pow(iG,(mod-1)/(i<<1));}il vd add(int&a,int b){a=a+b>=mod?a+b-mod:a+b;}int fact[20000010],ifact[20000010];int pr[4000010],Pr,PL[20000010];bool yes[20000010];int main(){#ifdef XZZSB freopen("in.in","r",stdin); freopen("out.out","w",stdout);#endif poly_init(); int N=gi(),M=gi(),S=gi(),L=gi(),o=std::max(N,L); fact[0]=1;for(int i=1;i<=o;++i)fact[i]=1ll*i*fact[i-1]%mod; ifact[o]=pow(fact[o],mod-2);for(int i=o-1;~i;--i)ifact[i]=1ll*ifact[i+1]*(i+1)%mod; PL[0]=0,PL[1]=1; for(int i=2;i<=L;++i){ if(!yes[i])pr[++Pr]=i,PL[i]=pow(i,L); for(int j=1;j<=Pr&&i*pr[j]<=L;++j){ yes[i*pr[j]]=1; PL[i*pr[j]]=1ll*PL[pr[j]]*PL[i]%mod; if(i%pr[j]==0)break; } } poly f(L+1),g(L+1); for(int i=0,mul=1;i<=L;++i,mul=mod-mul)f[i]=1ll*mul*ifact[i]%mod; for(int i=0;i<=L;++i)g[i]=1ll*PL[i]*ifact[i]%mod; f=mul(f,g,L+1); while(S--){ int n=gi(),m=gi(),k=gi(),ans=0,o=std::min(k,std::min(m,L)); for(int i=0;i<=o;++i) ans=(ans+1ll*f[i]*ifact[m-i]%mod*fact[n-i]%mod*ifact[k-i])%mod; printf("%d\n",1ll*ans*fact[m]%mod*fact[k]%mod*ifact[n]%mod); } return 0;}